Just Long Neckties 2

문제

Just Odd Inventions Co., Ltd. is a company renowned for doing ”just odd inventions.” Here we just call it JOI Company.

To celebrate the 5th anniversary of their flagship product, ”Just Long Neckties,” JOI Company has invented a new product: ”Just Stretchable Neckties.” As its name suggests, this new necktie has the unique feature of being able to extend its length indefinitely.

JOI Company has decided to hold a showcase event to promote the new necktie, and you have been selected as the host of the event. At the event, several models wearing the new neckties will appear on stage. Initially, the length of every necktie worn by the models is set to $11$.

After that, you will carry out a total of $NN$ performances to demonstrate the necktie’s stretchable feature to the audience. Each performance is conducted as follows:

1. First, you ask the audience to call out a number of their choice. Let this number be $xx$.
2. Next, you decide whether to respond or ignore it.
   • If you choose to respond to it, you must select one of the models on stage whose necktie length is currently less than or equal to $xx$ and set the length of that model’s necktie to exactly $xx$. (Note that you may select a model whose necktie length is already $xx$.) However, if no model can be selected, the showcase event will fail.
   • If you choose to ignore it, you do nothing.

However, if you ignore the audience’s number two or more times in a row, the audience will get angry, and the showcase event will fail.

The number of models on stage, denoted as $kk$ (k ≥ 1), has not yet been determined. Since hiring models costs considerable money, it is desirable to keep $kk$ as small as possible. The minimum value of $kk$ required to prevent the showcase event from failing depends on the numbers called out by the audience during the performances. Fortunately, you possess precognitive abilities and have foreseen that the number called out by the audience during the $ii$-th performance (1 ≤ i ≤ N) will be $A_{i}A\_i$.

Write a program which, given the numbers called out by the audience during the showcase event, calculates the minimum number of models $kk$ required to prevent the showcase event from failing.

입력

Read the following data from the standard input.

$NN$

$A_{1}A\_1$ $A_{2}A\_2$ $\cdots \backslash cdots$ $A_{N}A\_N$

출력

Write one line to the standard output. The output should contain the minimum number of models $kk$ required to prevent the showcase event from failing.

5
5 3 4 2 1

2

6
2 1 1 2 2 1

1

10
2 4 6 7 4 5 5 3 4 1

3