P6726: 老师的饭店（restaurant）
传统题
1.000s
时间限制
128MB
内存限制
0 提交
0 解决
【题目描述】
【题目背景】生活不易，老师也是需要养家糊口的。最近老师开了一家饭店。
【题目描述】
老师的饭店最多可以招待 n 个人，对应的编号从 0 ∼ n − 1。
这 n 个客人坐在一个只能逆时针旋转的巨大圆桌，每个人前面都会摆上一道佳肴。开始的时候，编号为 i 的人面前摆正的佳肴编号为 pi。
当且仅当满足以下条件，我们称为幸福的。
l 第 i 道佳肴恰好在编号第 (i − 1) mod n 的人，编号为 i 的人，或者编号为 (i + 1) mod n 的人。
现在你一种魔法：该魔法可以逆时针方向任意旋转圆桌一下。这样原来在编号为 i 的佳肴，将旋转到编号为 (i + 1) mod n 的人前面。
你可以任意次使用该魔法，问经过这些操作后，最大幸福数是多少？
【输入格式】
从文件 restaurant.in 中读入数据。
输入一共包括 2 行。
第 1 行为一个正整数 n，表示老师的饭店最多可以容纳 n 人。
第 2 行包括 n 个正整数。第 i 个数为编号为 i 的人面前摆的佳肴编号 pi。
请注意：编号从 0 开始。
【输出格式】
输出到文件 restaurant.out 中。
输出一行包括一个正整数，表示最大的幸福数。
【样例 1 输入】
4
1 2 0 3
【样例 1 输出】
4
【样例 1 解释】
图片中，左边图片显示了饭店的初始状态，右边图片显示最终的操
作。
这样，一共有 4 个人感觉幸福。
l 编号为 0 的人是幸福的，因为编号为 0 的佳肴在编号为 3 (= (0 − 1) mod 4) 的人前面。
l 编号为 1 的人是幸福的，因为编号为 1 的佳肴在编号为 1 (= 1) 的 人前面。
l 编号为 2 的人是幸福的，因为编号为 2 的佳肴在编号为 2 (= 2) 的 人前面。
l 编号为 3 的人是幸福的，因为编号为 3 的佳肴在编号为 0 (= (3 + 1) mod 4) 的人前面。
所以对应的答案为 4。
【样例 2 输入】
3
0 1 2
【样例 2 输出】
3
【样例 3 输入】
10
3 9 6 1 7 2 8 0 5 4
【样例 3 输出】
5
【数据范围】
3 ≤ n ≤ 2 × 10^5；
0 ≤ pi ≤ n − 1；
pi≠pj，当 i≠j；
所有的数据都是整数，保证输入数据合法。