AT_discovery_2016_qual_b ディスコ社内ツアー

你是 DISCO presents 发现频道编程竞赛 2016 决赛中 DISCO 公司内部参观的导游。 在公司内部参观中，需要带领参观的房间有 $N$ 个，每个房间被分配了从 $1$ 到 $N$ 的编号。建筑的结构是环形的，从第 $i$ 个房间（$1 \leq i \leq N-1$）可以移动到第 $i+1$ 个房间。从第 $N$ 个房间可以移动到第 $1$ 个房间。这些通道都是单向的，不能反向移动。 当你在第 $i$ 个房间时，可以选择参观该房间，或者移动到下一个房间。但是，为了避免让参与者感到厌倦，每个房间只能参观一次。你凭借多年带团经验，知道参观第 $i$ 个房间时获得的有趣程度可以用一个整数 $A_i$ 表示。 公司内部参观必须从第 $1$ 个房间出发，在参观完所有房间后，最终回到第 $1$ 个房间结束。为了让参与者更好地享受参观，你希望参观的房间的有趣程度按参观顺序排列时，是一个广义单调递增序列。在这样的限制下，进行公司内部参观时，至少需要在建筑内绕行多少圈？ 这里，如果一个有 $n$ 项的数列 $a$ 满足 $a_1 \leq a_2 \leq \dots \leq a_n$，则称 $a$ 是广义单调递增序列。另外，从第 $1$ 个房间出发，依次经过所有房间各一次并回到第 $1$ 个房间，称为绕建筑一圈。

输入通过标准输入按以下格式给出。 > $N$ > $A_1\ A_2\ \dots\ A_N$ - 第 $1$ 行给出需要参观的房间数 $N$，满足 $2 \leq N \leq 10^5$。 - 第 $2$ 行给出每个房间参观时的有趣程度 $A_i$，满足 $1 \leq A_i \leq 10^5$，以空格分隔。

请输出在满足给定条件下进行公司内部参观所需的最少圈数。输出一行，末尾需换行。

### 部分分 本题设有部分分。 - 对于满足 $2 \leq N \leq 100$ 的数据集，得 $20$ 分。 - 对于满足 $1 \leq A_i \leq N$ 且 $i \neq j$ 时 $A_i \neq A_j$ 的数据集，除上述部分分外，另得 $10$ 分。 - 对于无额外限制的数据集，另得 $70$ 分。 ### 样例解释 1 - 通过如下顺序参观，可以在 $3$ 圈内完成公司内部参观。从第 $1$ 个房间出发，立即参观第 $1$ 个房间是允许的。注意，参观结束时必须在所有房间参观完毕且回到第 $1$ 个房间。 - 第 $1$ 圈参观第 $1$ 个房间和第 $4$ 个房间。 - 第 $2$ 圈参观第 $3$ 个房间。 - 第 $3$ 圈参观第 $2$ 个房间和第 $5$ 个房间。 - 本例同时满足上述部分分的第 $1$ 个和第 $2$ 个条件。 ### 样例解释 2 - 第 $1$ 圈即可参观所有房间。 - 本例同时满足上述部分分的第 $1$ 个和第 $2$ 个条件。 ### 样例解释 3 - 在最后一次参观第 $1$ 个房间后立即结束参观，可以在 $1$ 圈内完成。 - 本例同时满足上述部分分的第 $1$ 个和第 $2$ 个条件。 ### 样例解释 4 - 注意有些房间的有趣程度是重复的。 - 本例仅满足上述部分分的第 $1$ 个条件，不满足第 $2$ 个条件。 由 ChatGPT 4.1 翻译