题目描述

有$𝑁$张牌编号分别为$1, 2, … , 𝑁$。 首先把这$𝑁$张牌打乱排成一排，然后我们要做一次旋转使得 旋转后固定点尽可能多。写一个程序，找到这样的子段。

旋转的定义： 旋转可以被认为是将其中的一个子段旋转$180$度，这意味着子段的第一张卡和 最后一张卡交换位置，第二张牌和倒数第二张牌交换位置，等等。

固定点的定义： 如果第$𝑖$个位置的牌的编号为$𝑖$，我们就𝑖为固定点。

输入格式

输入的第一行包含一个整数 $𝑁 (1 ≤ 𝑁 ≤ 5 × 10^5)$。

输入的第二行有$𝑁$个数，第$𝑖$个数表示旋转之前第$𝑖$个位置的牌$sd$的编号。

输出格式

找到固定点最多旋转子段，输出固定点的个数

4
3 2 1 4

4

2
1 2

2

7
3 6 5 7 4 1 2

2

样例解释

对于样例一，旋转子段$[1, 3]$，序列变成$1 2 3 4$，所有位置都是固定点，答案为$4$。

对于样例二，不用旋转就可以使得固定点为$2$，因此选择任意一个长度为$1$的区间旋转即可。

数据范围与提示

存在$30$的测试样例满足$𝑁 ≤ 500$。

另有$30$测试样例满足$𝑁 ≤ 5000$。

另有$40$测试样例满足$𝑁 ≤ 60000$。