Card Rotation Fixed Points

Mate is playing a modified version of the card game Hanabi. He holds N cards numbered from \(1\) to \(N\) in a fixed order (i.e. a permutation of \(\{1,2,\ldots,N\}\)). Domagoj, who adores fixed points (positions where the card number equals its position in the hand, counting from 1), is allowed to choose a contiguous subarray of cards. Mate then rotates (i.e. reverses) the chosen subarray. In other words, if the chosen subarray is from index \(l\) to \(r\) (1-indexed), then the card originally at position \(l\) goes to position \(r\), the card originally at position \(l+1\) goes to position \(r-1\), and so on.

After the rotation the fixed points are those indices \(i\) for which the card value is \(i\). Domagoj wants to maximize the number of fixed points after the rotation. Your task is to find the maximum possible number of fixed points that can be obtained by choosing an appropriate contiguous subarray to rotate.

It can be shown that the best you can do is to increase the number of fixed points by at most 2. In particular, if the original sequence already has base fixed points, then:

• If there exists a pair of indices \(i\) and \(j\) (that are not fixed originally) such that \(A[i]=j\) and \(A[j]=i\) (with indices considered in 1-indexing), then the answer is \(\text{base}+2\).
• Otherwise, if there exists some index \(i\) which is not a fixed point and can be fixed by an appropriate reversal, then the answer is \(\text{base}+1\).
• If all cards are already fixed then the answer remains \(\text{base}\).

Note on indices: The input positions are 1-indexed. However, in many programming languages arrays are 0-indexed.

Mathematical formulation:
Let the permutation be \(A = [A_1, A_2, \dots, A_N]\) with the property that each number from 1 to \(N\) appears exactly once. After choosing a contiguous subarray from \(l\) to \(r\) and reversing it, the new sequence \(B\) is given by:

[ B_i = \begin{cases} A_i & \text{if } i < l \text{ or } i > r,\ A_{l+r-i} & \text{if } l \le i \le r. \end{cases} ]

You need to maximize \(\sum_{i=1}^{N} [B_i = i]\), where \([B_i = i]\) is 1 if \(B_i=i\) and 0 otherwise.

inputFormat

The first line contains a single integer \(N\) \( (1 \le N \le 10^5)\) representing the number of cards. The second line contains \(N\) space-separated integers, representing the permutation \(A_1, A_2, \dots, A_N\).

outputFormat

Output a single integer — the maximum number of fixed points that can be obtained after performing the reversal operation on one contiguous subarray.

sample

4
2 1 4 3

2