C. Superior Periodic Subarrays

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

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 < n$, $1 ≤ s < 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.

Орчуулсан: [орчуулагдаж байгаа]

Жишээ тэстүүд

Оролт
4
7 1 2 3
Гаралт
2
Оролт
2
2 1
Гаралт
1
Оролт
3
1 1 1
Гаралт
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.

Сэтгэгдлүүдийг ачааллаж байна...