問題文
您是 DISCO 呈现探索频道编程大赛 2016 年主赛事 DISCO 内部巡演的导游。
公司参观中展示的房间是 N 有地点,每个房间都有 编号 1 减去 N 已分配。建筑结构呈圆形, 来自 i(1≦i≦N-1) 号房间 i+1 个房间。 从第 N 号房间 您可以移动到第 1个房间。这些道路是单向的,您不能朝相反的方向行驶。 当您位于第
i 个房间时,您可以选择游览该房间或移动到下一个房间。然而,如果参与者一遍又一遍地参观同一个房间,他们会感到无聊,因此应该针对每个房间单独进行参观。 1 只能完成一次。 根据您多年组织公司参观的经验, 当您访问第 i个房间时获得的乐趣是一个整数。 我知道它是由 A_i 代表的。
公司参观 1 从第一个房间开始,参观完所有房间。 您最终必须到达第 1 个房间。 为了让参与者享受您公司的游览,您决定根据他们参观的房间的有趣程度以单调递增的顺序引导他们参观房间。 在这些限制下进行公司参观时,围绕建筑物的最少圈数是多少?
在这里, 由 n 项组成的序列 当满足 a 的 a_1 ≦ a_2 ≦ ... ≦ a_n 时, a 据说是一个广泛单调递增的序列。 另外, 从第 1 个房间移动并打开所有房间。 1 每次访问 1 大楼回到第号房间 1 这叫绕来绕去。
入力
输入是按以下格式从标准输入给出的。
N A_1 A_2 … A_N
- 1 引导至行的房间数 N (2≦N≦10^{5}) 。 表示
- 2 该行中的一个整数,表示每个房间在游览时的有趣程度。 A_i (1≦A_i≦10^{5}) 用空格分隔。
出力
计算满足给定条件进行内部游览所需的最少圈数。 在 1 行输出。不要忘记最后的换行符。 如果正确答案是满足
部分点
针对此问题设置了部分分数。
- 2≦N≦100 的数据集 在 20 点。 如果您正确回答了所有满足
- 1≦A_i≦N和i≠j中 如果A_i≠A_j在成立的数据集中正确回答,除了上述部分点之外, 10 点。 如果您正确回答了所有满足
- 如果答案对于没有附加约束的数据集是正确的,则进一步 获得 70 点。
入力例 1
5 1 4 3 2 5
出力例 1
3
- 按以下顺序进行游览, 3 可以在几圈内完成公司参观。 1 从第号房间开始,立即 您可以参观第 1 个房间。参观完所有房间后,旅程开始。 请注意,您最终必须到达房间号 1 。
- 1 第三轮, 1 第一个房间和 参观第 4 个房间。
- 2 第三轮, 3 个房间。
- 3 第三轮, 2 第一个房间和 参观第 5 个房间。
- 在这种情况下,以上部分要点 1 第二个条件和 2 满足第一个条件。
入力例 2
5 1 2 3 4 5
出力例 2
1
- 1 第一周可以参观所有房间。
- 在这种情况下,以上部分要点 1 第二个条件和 2 满足第一个条件。
入力例 3
5 5 1 2 3 4
出力例 3
1
- 最后 参观 1 第一个房间后立即结束游览 1 可以以圈为单位结束游览。
- 在这种情况下,以上部分要点 1 第二个条件和 2 满足第一个条件。
入力例 4
8 1 1 1 2 2 2 3 3
出力例 4
1
- 请注意,部分房间的兴趣重叠。
- 在这种情况下,以上部分要点 1 满足第二个条件。 2 不满足第一个条件。