Superior Periodic Subarrays

题意翻译

给定一个循环节长度为 $n$ 的无限循环数列 $a$，定义 $(l,s)$ 表示起点为 $l$ 的长度为 $s$ 的子串。 称一组 $(l,s)$ 是合法的，当且权当该子串从 $l$ 开始以 $s$ 为循环节长度的无限循环数列中的每个数都大于等于原数列中对应位置的数。 你需要求出合法的 $(l,s)$ 组数。$(0 \leq l \leq n,1 \leq s \leq n)$

题目描述

You are given an infinite periodic array $ a_{0},a_{1},...,a_{n-1},... $ with the period of length $ n $ . Formally, . A periodic subarray $ (l,s) $ ( $ 0<=l&lt;n $ , $ 1<=s&lt;n $ ) of array $ a $ is an infinite periodic array with a period of length $ s $ that is a subsegment of array $ a $ , starting with position $ l $ . A periodic subarray $ (l,s) $ is superior, if when attaching it to the array $ a $ , starting from index $ l $ , any element of the subarray is larger than or equal to the corresponding element of array $ a $ . An example of attaching is given on the figure (top — infinite array $ a $ , bottom — its periodic subarray $ (l,s) $ ): Find the number of distinct pairs $ (l,s) $ , corresponding to the superior periodic arrays.

输入输出格式

输入格式

The first line contains number $ n $ ( $ 1<=n<=2·10^{5} $ ). The second line contains $ n $ numbers $ a_{0},a_{1},...,a_{n-1} $ ( $ 1<=a_{i}<=10^{6} $ ), separated by a space.

输出格式

Print a single integer — the sought number of pairs.

输入输出样例

输入样例 #1

4
7 1 2 3

输出样例 #1

2

输入样例 #2

2
2 1

输出样例 #2

1

输入样例 #3

3
1 1 1

输出样例 #3

6

说明

In the first sample the superior subarrays are (0, 1) and (3, 2). Subarray (0, 1) is superior, as $ a_{0}>=a_{0},a_{0}>=a_{1},a_{0}>=a_{2},a_{0}>=a_{3},a_{0}>=a_{0},... $ Subarray (3, 2) is superior $ a_{3}>=a_{3},a_{0}>=a_{0},a_{3}>=a_{1},a_{0}>=a_{2},a_{3}>=a_{3},... $ In the third sample any pair of $ (l,s) $ corresponds to a superior subarray as all the elements of an array are distinct.