A. Two Subsequences
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation $$$p$$$ of integers $$$1$$$ to $$$n$$$. You need to partition $$$p$$$ into two disjoint increasing subsequences such that the difference between the sizes of these subsequences is the maximum possible. Note that each element must belong to exactly one of the subsequences. The empty subsequence is also allowed.

Input

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$), the number of elements in the permutation. The second line contains $$$n$$$ integers $$$p_i$$$ ($$$1 \leq p_i \leq n$$$), where the $$$i$$$-th of them equals the $$$i$$$-th element of the permutation. It is guaranteed that each integer from $$$\{1, \ldots, n\}$$$ appears exactly once among $$$p_i$$$.

Output

Output a single integer, the maximum difference of sizes of subsequences. If it is not possible to partition the permutation into two disjoint increasing subsequences, output $$$-1$$$.

Examples
Input
2
2 1
Output
0
Input
4
4 2 3 1
Output
-1
Input
10
2 4 5 1 6 3 7 8 9 10
Output
6
Input
11
1 2 3 4 5 6 7 8 9 10 11
Output
11