← 返回题目列表

AtCoder · abc268_c

F. 中餐厅

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

人 0, 人 1, \ldots和人 (N-1) 按逆时针顺序坐在转盘周围,间隔均匀。 菜品 p_i 位于 Person 前面 i 在桌子上。
您可以执行以下操作 0 或多次:

  • 将转盘旋转一圈 N- 逆时针旋转一圈。 结果,摆在Person面前的菜 i 旋转之前现在位于 Person 的前面 (i+1) \bmod N.

当你完成后,Person i 如果菜很高兴 i 位于 Person 前面 (i-1) \bmod N, 人 i或人 (i+1) \bmod N.
找到快乐的人的最大可能数量。

什么是 a \bmod m? 对于整数 a 和一个正整数 m, a \bmod m 表示整数 x 之间 0 和 (m-1) (含)使得 (a-x) 是的倍数 m。 (可以证明这样 x 是唯一的。)

约束

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

输入

输入由标准输入按以下格式给出:

N
p_0 \ldots p_{N-1}

输出

打印答案。


示例输入 1

4
1 2 0 3

示例输出 1

4

下图为一次操作后的表格。

这里有四个快乐的人:

  • 人 0 很高兴,因为菜 0 位于 Person 前面 3\ (=(0-1) \bmod 4);
  • 人 1 很高兴,因为菜 1 位于 Person 前面 1\ (=1);
  • 人 2 很高兴,因为菜 2 位于 Person 前面 2\ (=2);
  • 人 3 很高兴,因为菜 3 位于 Person 前面 0\ (=(3+1) \bmod 4).

幸福的人不可能有五个或更多,所以答案是 4.


示例输入 2

3
0 1 2

示例输出 2

3

示例输入 3

10
3 9 6 1 7 2 8 0 5 4

示例输出 3

5