给定一个无限周期数组 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) 对都对应于上级子数组,因为数组的所有元素都是不同的。