Дан бесконечный периодический массив a0, a1, ..., an - 1, ... с периодом длины n. Формально, 
. Периодическим подмассивом (l, s) (0 ≤ l < n, 1 ≤ s < n) массива a называется бесконечный периодический массив с периодом длины s, период которого является подотрезком массива a, начинающегося с позиции l.
Периодический подмассив (l, s) называется превосходящим, если при совмещении его с массивом a, начиная с индекса l, любой элемент подмассива оказывается большим либо равным соответствующего ему в совмещении элемента массива a. Пример совмещения представлен на рисунке (сверху — бесконечный массив a, снизу — его периодический подмассив (l, s)):
Найдите количество различных пар (l, s), соответствующих превосходящим периодическим подмассивам.
Выходные данные
Выведите единственное число — искомое количество пар.
Примечание
В первом примере превосходящими являются подмассивы (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) соответствует превосходящему подмассиву, так как все элементы массива равны.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
7 1 2 3
|
2
|
|
2
|
2
2 1
|
1
|
|
3
|
3
1 1 1
|
6
|