Given a sequence of length $n$, you need to find the longest subsequence such that the length of its longest increasing subsequence is strictly less than the length of the longest increasing subsequence of the original sequence.

Input

The first line contains a positive integer $n$.

The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$.

Output

A single line containing a positive integer, representing the length of the longest valid subsequence.

Examples

Input 1

6
4 6 5 2 1 3

Output 1

4

Input 2-7

See the provided files.

Constraints

For all data, $1 \le n \le 5 \times 10^5$, $1 \le a_i \le 10^9$.