Problem: Russian Dolls

Want to try solving this problem? You can submit your code online if you log in or register.

Russian Dolls

Input File: dollin.txt
Output File: dollout.txt
Time Limit: 1 second

Matryoshka doll sets are Russian toys that are constructed from several dolls of various sizes, designed to fit inside each other. Each doll's size is a positive integer. A doll of size k can fit a single doll inside it of size k-1 or smaller. Nothing will fit inside a doll of size 1.

You work on the assembly line of a Matryoshka doll factory, where your job is to assemble the dolls into sets for sale. On the assembly line is a continuous conveyor belt. Each pass of the conveyor belt allows you to build one set of dolls. Normally, each pass of the conveyor belt brings N new dolls lined up from largest to smallest, as shown in the diagram below. The dolls come off the conveyor belt in the order 6, 5, 4, 3, 2, 1.

$\includegraphics[width=10cm]{dollgood}$

Your routine is to pick up the first doll off the belt, the largest, and place it in front of you. You then pick up the second doll and put it inside the one in front of you, and so on until the final and smallest doll is placed inside and the set is complete. When the conveyor belt is empty, a new set of dolls appears on the line.

However, in the rush to fill orders for Christmas, disaster has struck! One set of dolls has been manufactured out of order--instead of arriving from largest to smallest, they arrive in a random order, preventing you from putting the pieces into one set. You decide to assemble the smallest possible number of doll sets, complete or not, that use all the pieces on the conveyor belt.

For each pass of the conveyor belt you must construct a set of dolls by selecting some of the dolls on the belt. The dolls you choose for each set must be in decreasing order of size on the conveyor belt. At the end of each pass, a set must be placed in its box, regardless of how many dolls made up the set. The remaining dolls will do another pass of the conveyor belt, allowing you to construct another set, and so on, until there are no more dolls on the conveyor belt.

$\includegraphics[width=10cm]{dollbad}$

Consider the set of dolls illustrated above that have been placed on the conveyor belt out of order. They arrive in the order 3,2,6,4,5,1. To rectify this situation, you could first choose the dolls sized 6 and 4 on the first pass to construct the first set, then dolls 3, 2 and 1 on the second pass to construct the second set, and finally doll 5 on the third pass to construct a third set. This creates three sets of dolls, which is the smallest number that can be constructed in this case. Note that there are several other ways in which three sets can be constructed--for example, you could choose dolls 3 and 2, then dolls 6 and 4, and finally dolls 5 and 1.

Your task is to determine the smallest number of doll sets that can be constructed, given the order of doll sizes.

Input

The first line of the input file will contain a single integer N, the number of dolls that make up a complete Matryoshka doll set ( 1 <= N <= 1000000). The following N lines contain the integers k_1, k_2, ..., k_N, one per line, where k_i is the size of the ith doll to appear. Each k_i will be between 1 and N, inclusive, and no two values of k_i will be the same.

Output

The output file should contain a single integer S, the smallest number of doll sets that can be constructed from the dolls on the conveyor belt.

Sample Input

Sample Output

Scoring

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.