C - 中餐馆

得分为 $300$ 分

题目描述

编号为 $0$ 的人，编号为 $1$ 的人，$\ldots$，编号为 $(N-1)$ 的人逆时针顺序坐在一张圆桌周围，等距离的分布。第 $i$ 个人前面放着第 $p_i$ 个盘子。
你可以进行 $0$ 次或多次以下操作：

• 把圆桌逆时针旋转一个 $N$ 分之一圈。这样，在旋转之前，第 $i$ 个人前面的盘子现在在第 $(i+1) \bmod N$ 个人前面。

当你结束操作后，如果第 $i$ 盘菜在第 $(i-1)\bmod N$ 个人、第 $i$ 个人或第 $(i+1)\bmod N$ 个人面前，第 $i$ 个人就会感到高兴。 找出最多可能的开心人数。

限制

• $3 \leq N \leq 2 \times 10^5$
• $0 \leq p_i \leq N-1$
• 当 $i \neq j$ 时，$p_i \neq p_j$。
• 输入中的所有值都是整数。

输入

输入从标准输入中获取，具有以下格式：

$N$

$p_0$ $\ldots$ $p_{N-1}$

输出

打印答案。

4
1 2 0 3

4

下图显示了进行一次操作后的桌子。

这里，有四个开心的人：

• 编号为 $0$ 的人开心，因为盘子 $0$ 在编号为 $3\ (=(0-1) \bmod 4)$ 的人前面；
• 编号为 $1$ 的人开心，因为盘子 $1$ 在编号为 $1\ (=1)$ 的人前面；
• 编号为 $2$ 的人开心，因为盘子 $2$ 在编号为 $2\ (=2)$ 的人前面；
• 编号为 $3$ 的人开心，因为盘子 $3$ 在编号为 $0\ (=(3+1) \bmod 4)$ 的人前面。

不能有五个或更多的开心的人，所以答案是 $4$。

3
0 1 2

3

10
3 9 6 1 7 2 8 0 5 4

5