You are given an infinite periodic array a0, a1, ..., an - 1, ... with the period of length n. Formally, <image>. 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)):

<image>

Find the number of distinct pairs (l, s), corresponding to the superior periodic arrays.

Input

The first line contains number n (1 ≤ n ≤ 2·105). The second line contains n numbers a0, a1, ..., an - 1 (1 ≤ ai ≤ 106), separated by a space.

Output

Print a single integer — the sought number of pairs.

Examples

Input

4
7 1 2 3


Output

2


Input

2
2 1


Output

1


Input

3
1 1 1


Output

6

Note

In the first sample the superior subarrays are (0, 1) and (3, 2).

Subarray (0, 1) is superior, as a0 ≥ a0, a0 ≥ a1, a0 ≥ a2, a0 ≥ a3, a0 ≥ a0, ...

Subarray (3, 2) is superior a3 ≥ a3, a0 ≥ a0, a3 ≥ a1, a0 ≥ a2, a3 ≥ a3, ...

In the third sample any pair of (l, s) corresponds to a superior subarray as all the elements of an array are distinct.
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.util.ArrayList;
import java.math.BigDecimal;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.io.IOException;
import java.math.MathContext;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author ilyakor
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }
}

class TaskC {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i)
            a[i] = in.nextInt();
        long res = getRes(n, a);
        out.printLine(res);

    }

    public long getRes(int n, int[] a) {
        ArrayList<Integer>[] ss = new ArrayList[n];
        for (int i = 0; i < n; ++i) {
            ss[i] = new ArrayList<>();
        }
        for (int s = 1; s < n; ++s)
            ss[IntegerUtils.gcd(s, n)].add(s);

        int[] groups = new int[n + 10];
        int gcnt;
        long res = 0;
        for (int d = 1; d < n; ++d) {
            if (n % d != 0) continue;
            int[] mx = new int[d];
            for (int i = 0; i < n; ++i) {
                if (mx[i % d] < a[i])
                    mx[i % d] = a[i];
            }
            gcnt = 0;
            int cur = 0;
            long sum = 0;
            for (int i = 0; i < n; ++i) {
                if (a[i] == mx[i % d])
                    ++cur;
                else {
                    groups[gcnt++] = cur;
                    sum += cur;
                    cur = 0;
                }
            }

            if (cur == n) {
                res += (long) ss[d].size() * (long) n;
                continue;
            }

            if (cur > 0) {
                if (a[0] == mx[0] && cur < n) {
                    groups[0] += cur;
                } else {
                    groups[gcnt++] = cur;
                }
                sum += cur;
            }

            Arrays.sort(groups, 0, gcnt);
            int pos = 0;
            int prev = 1;
            for (int x : ss[d]) {
                while (pos < gcnt && groups[pos] < x) {
                    sum -= groups[pos] - prev + 1;
                    ++pos;
                }
                sum -= (long) (x - prev) * (long) (gcnt - pos);
                res += sum;
                prev = x;
            }
        }

return res;
    }

}

class InputReader {
    private InputStream stream;
    private byte[] buffer = new byte[10000];
    private int cur;
    private int count;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public static boolean isSpace(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public int read() {
        if (count == -1) {
            throw new InputMismatchException();
        }
        try {
            if (cur >= count) {
                cur = 0;
                count = stream.read(buffer);
                if (count <= 0)
                    return -1;
            }
        } catch (IOException e) {
            throw new InputMismatchException();
        }
        return buffer[cur++];
    }

    public int readSkipSpace() {
        int c;
        do {
            c = read();
        } while (isSpace(c));
        return c;
    }

    public int nextInt() {
        int sgn = 1;
        int c = readSkipSpace();
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res = res * 10 + c - '0';
            c = read();
        } while (!isSpace(c));
        res *= sgn;
        return res;
    }

}

class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public void print(Object... objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0) {
                writer.print(' ');
            }
            writer.print(objects[i]);
        }
    }

    public void printLine(Object... objects) {
        print(objects);
        writer.println();
    }

    public void close() {
        writer.close();
    }

}

class IntegerUtils {
    public static int gcd(int x, int y) {
        if (y == 0) return x;
        return gcd(y, x % y);
    }

}

