#881. T5

T5

题目描述

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

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

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

输入格式

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

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

输出格式

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

4
3 2 1 4
4
2
1 2
2
7
3 6 5 7 4 1 2
2

样例解释

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

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

数据范围与提示

存在3030%的测试样例满足𝑁500𝑁 ≤ 500

另有3030%测试样例满足𝑁5000𝑁 ≤ 5000

另有4040%测试样例满足𝑁60000𝑁 ≤ 60000