A. Reverse Pairs Coloring
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

We know the definition of reverse pairs: for a permutation $$$a_1,a_2,\dots,a_n$$$ of length $$$n$$$, if there exists $$$i \lt j$$$ and $$$a_i \gt a_j$$$, then $$$a_i,a_j$$$ form a reverse pair. A permutation of length $$$n$$$ contains each of the numbers $$$1$$$ to $$$n$$$ exactly once.

Finding the number of reverse pairs should not be a difficult task for you. Now, you are given a permutation $$$a_1,a_2,\dots,a_n$$$ of length $$$n$$$. For each pair satisfying $$$i \lt j$$$ and $$$a_i \gt a_j$$$ of reverse pairs, color the cell in the $$$n \times n$$$ grid at row $$$i$$$ and column $$$a_j$$$. Please determine how many colored connected components are there in the final grid. Connected means that if two colored cells share an edge, then we consider these two cells to be connected.

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 3 \times 10^5$$$), representing the length of the permutation.

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$, representing a permutation of length $$$n$$$.

Output

Output an integer, representing the number of four-connected components in the final grid.

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