Bob the ghost observes a line of ~N~ distinct houses, each containing a lit jack o' lantern labelled by a (not necessarily distinct) integer ~1 \leq x_i \leq N~. Bob floats from ~x_1~ to ~x_N~ across the line of houses from one end to the other, and since Bob despises happiness, he extinguishes each jack o' lantern in order from least to greatest (he cannot skip any numbers). Assume Bob teleports to the start (leftmost point) after every pass. How many passes does he need in total to extinguish every jack o' lantern?

Input Specification

The first line of input contains one integer ~N~, representing the number of houses on the street.

The second line of input contains ~N~ space-separated integers ~x_i (1 \leq i \leq N)~, representing the integer associated with each jack o' lantern.

Output Specification

Output one integer, indicating the least number of passes Bob needs to extinguish all jack o' lanterns.

Constraints

For all subtasks, ~1 \leq x_i \leq N~

Subtask 1 [5%]

~1 \leq N \leq 2~

Subtask 2 [25%]

~1 \leq N \leq 10^3~

Subtask 3 [70%]

~1 \leq N \leq 10^6~

Sample Input

7
1 2 5 5 4 1 3

Sample Output

4

Sample Explanation

During Bob's first pass, he extinguishes the ~1^{st}~ and ~6^{th}~ jack o' lantern. During Bob's second pass, he extinguishes the ~2^{nd}~ and ~7^{th}~ jack o' lantern. During Bob's third pass, he extinguishes the ~5^{th}~ jack o' lantern. Finally, during Bob's fourth pass, he extinguishes the remaining ~3^{rd}~ and ~4^{th}~ jack o' lantern.