Minimum k for a Successful Performance Show

You are given a sequence of $N$ positive integers $A_1,A_2,\ldots,A_N$ representing numbers called out by the audience over $N$ shows. You also have an initially unknown-length integer sequence $B_1,B_2,\ldots,B_k$ (with $k\ge 1$) where initially $B_i=1$ for all $1\le i\le k$. During each show $i$ (from $1$ to $N$), you may choose to either respond or skip. If you choose to respond at show $i$, you must select an index $j$ ($1\le j\le k$) satisfying

[ B_j \le A_i ]

and update that slot with:

[ B_j \leftarrow A_i. ]

If there is no such index, the performance fails. If you choose to skip, nothing changes; however, if you ever skip for two (or more) consecutive shows, the performance fails. Under the guarantee that a strategy exists that avoids failure, determine the minimum value of $k$ (the minimum number of slots in $B$) for which a valid strategy exists.

A valid strategy is a choice of reply/skip decisions (with the constraint that you never skip in two consecutive shows) and, when responding, choosing an index to update (subject to $B_j \le A_i$) so that all $N$ shows can be processed without failure.

Note that when you respond, you update one of the $B$ values. Over the course of the performance, the sequence of responses (i.e. the sequence of $A_i$ at the shows where you responded) must be such that it is possible to partition it into $k$ non–decreasing subsequences (since in each slot the updates are non–decreasing). By a classical result, the minimum number of non–decreasing subsequences required to partition a sequence equals the length of its longest (\emph{(strictly) decreasing}) subsequence. Hence, if you answered in shows forming a subsequence $S$, then your chosen strategy is successful if and only if the longest strictly decreasing subsequence of $(A_i : i \in S)$ is at most $k$, with the additional constraint that in the full (N) events the response pattern never has two consecutive skips (equivalently, the number of responses is at least (\lceil N/2\rceil)).

Your task is to compute the minimum (k) for which a valid strategy exists. It is guaranteed that a valid strategy exists if you choose (k) sufficiently large.

inputFormat

The first line contains an integer (N) (the number of shows). The second line contains (N) positive integers (A_1, A_2, \ldots, A_N) separated by spaces.

outputFormat

Output a single integer: the minimum (k) for which a valid strategy exists.

sample

2
100 1

1