← 返回题目列表

Codeforces · 582/C

C. 高级周期性子阵

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

给定一个无限周期数组 a0, a1, ..., an - 1, ... ,周期长度为 n。形式上,$$a_{i} = a_{i \bmod n}$$。数组 a 的周期子数组 (l, s) (0 ≤ l < n, 1 ≤ s < n) 是一个无限周期数组,周期长度为 s,是数组 a 的子段,从位置 l 开始。

如果将周期子数组 (l, s) 附加到数组 a 时,从索引 l 开始,子数组的任何元素都大于或等于数组 a 的相应元素,则该子数组 (l, s) 是优越的。图中给出了附加的示例(顶部 - 无限数组 a,底部 - 其周期子数组 (l, s)):

找出对应于上级周期数组的不同对 (l, s) 的数量。

输入

第一行包含数字 n (1 ≤ n ≤ 2·105)。第二行包含 n 个数字 a0, a1, ..., an - 1 (1 ≤ ai ≤ 106),用空格分隔。

输出

打印一个整数 — 所寻求的对数。

示例

输入 #1

4
7 1 2 3

输出 #1

2

输入 #2

2
2 1

输出 #2

1

输入 #3

3
1 1 1

输出 #3

6

注意

在第一个样本中,上级子数组是 (0, 1) 和 (3, 2)。

子数组 (0, 1) 更优越,因为 a0 ≥ a0, a0 ≥ a1, a0 ≥ a2, a0 ≥ a3, a0 ≥ a0, ...

子数组 (3, 2) 优于 a3 ≥ a3, a0 ≥ a0, a3 ≥ a1, a0 ≥ a2, a3 ≥ a3, ...

在第三个示例中,任何 (l, s) 对都对应于上级子数组,因为数组的所有元素都是不同的。