577. 翻转

单点时限: 5.0 sec

内存限制: 512 MB

QQ小方以前不会翻转数列,现在他会了,所以他急切的想教会你。

翻转数列指的是,把一个数列倒置。具体来说,如果一个数列是 $a_1,a_2,a_3\cdots a_n$ ,那么翻转以后的数列是 $a’1,a’_2,a’_3\cdots a’_n=a_n,a,a_{n-2}\cdots a_1$ 。

单单讲给你听肯定是不够的,为了表现自己,QQ小方现在要考考你。

现在QQ小方有一个数列 $a_1,a_2,a_3\cdots a_n$ 。他想要翻转数列中的其中一个子数列(一个数列的子数列指的是任意个连续的数组成的子序列,子序列可以为空)。而且他希望在翻转以后有尽量多的位置满足 $i=a’_i$ 。QQ小方想知道,经过一次翻转操作,数列中最多能有多少位置满足 $i=a’_i$ 。

输入格式

输入数据第一行包含一个整数 $n$ ( $1\le n\le 5\cdot 10^6$ ) ,表示数列的长度。

接下来的一行包含 $n$ 个用空格隔开的整数,分别表示 $a_1,a_2,a_3\cdots a_n$ ( $1\le a_i\le n$ ) ,表示初始的数列。

输出格式

输出一行包含一个整数,表示答案。

样例

Input
4
3 4 1 2
Output
2

提示

可以选择翻转 $[1,3]$ 子数列,变成 $1,4,3,2$ ,则位置 $1$ 和 $3$ 满足要求了。

也可以选择翻转 $[2,4]$ 子数列,变成 $3,2,1,4$ ,则位置 $2$ 和 $4$ 满足要求了。

没有更优的翻转方案了。

76 人解决,222 人已尝试。

93 份提交通过,共有 1307 份提交。

5.8 EMB 奖励。

创建: 2 年,6 月前.

修改: 1 年,6 月前.

最后提交: 1 周,1 天前.

来源: EOJ Monthly 2019.5

题目标签