C. Ultimate Huron Sorting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

One year after participating in the Donald Knuth 2020 contest and solving successfully the problem Huron Sorting, Enya started to think about new algorithms to sort permutations. After some thinking, she came with a novel idea: the Ultimate Huron Sorting.

Let's define a permutation as an array of size $$$n$$$, such that all the numbers between $$$1$$$ and $$$n$$$ appears exactly once in the permutation and it does not have any repeated element. For example, $$$[1,2,3,4]$$$ and $$$[3,1,4,2]$$$ are permutations of size $$$4$$$, but $$$[1,1,3,4]$$$ and $$$[3,2,1,5]$$$ are not.

To sort a permutation $$$A=[a_1, a_2, \dots, a_n]$$$ of size $$$n$$$ using the Ultimate Huron Sorting, Enya chooses an integer $$$x$$$, such that $$$1 \leq x \leq n$$$ at the beginning, and then perform the following operation any number of times until the permutation is sorted in increasing order:

  • Choose two different indices $$$i$$$ and $$$j$$$ ($$$1 \leq i,j \leq n$$$), such that $$$i \neq x$$$ and $$$j \neq x$$$, and swap the elements in the $$$i$$$-th and $$$j$$$-th positions of the permutation. In other words, Enya can choose any pair of indices different to the chosen $$$x$$$ and swap them.

Note that $$$x$$$ is always chosen at the beginning of the algorithm and does not change during its execution.

Enya quickly realized that this algorithm may not work for all values of $$$x$$$. Help her to find how many values of $$$x$$$ she can choose, such that she can apply some operations (possibly zero) to sort the permutation in increasing order.

Input

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 100$$$) $$$-$$$ size of the permutation.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$) $$$-$$$ the elements of the permutation.

Output

Print a single integer $$$-$$$ the number of suitable values of $$$x$$$.

Examples
Input
5
1 2 3 4 5
Output
5
Input
2
2 1
Output
0
Input
5
2 3 5 4 1
Output
1
Input
6
5 2 3 4 6 1
Output
3
Note

In the first example, the permutation is already sorted, so we can choose any value of $$$x$$$.

In the second example, we need to swap the first element with the second element to sort the permutation. If $$$x=1$$$, we can't choose the first element to sort the permutation. If $$$x=2$$$, we can't choose the second element to sort the permutation.

In the third example, the only value of $$$x$$$ that we can choose to sort the permutation is $$$4$$$. Let's see how we can sort this permutation with $$$x=4$$$:

  1. $$$[\textbf{2},3,5,\underline{4},\textbf{1}]$$$ - choose $$$i=1$$$ and $$$j=5$$$, and swap the element in those positions. We can choose those values since $$$x \neq 1$$$ and $$$x \neq 5$$$.
  2. $$$[1,\textbf{3},5,\underline{4},\textbf{2}]$$$ - choose $$$i=2$$$ and $$$j=5$$$, and swap the element in those positions.
  3. $$$[1,2,\textbf{5},\underline{4},\textbf{3}]$$$ - choose $$$i=3$$$ and $$$j=5$$$, and swap the element in those positions.
  4. $$$[1,2,3,\underline{4},5]$$$ - now the permutation is sorted in increasing order and we terminate the algorithm successfully.

You can try to order the permutation choosing any other value for $$$x$$$ and see that it is not possible.