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.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,mmx,sse,sse2")
using namespace std;
using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T, typename S>
inline ostream& operator<<(ostream& os, const pair<T, S> p) {
  cout << "[" << p.first << ";" << p.second << "]";
  return os;
}
template <typename T>
inline ostream& operator<<(ostream& os, const vector<T>& v) {
  for (auto el : v) cout << el << " ";
  return os;
}
template <typename T>
inline ostream& operator<<(ostream& os, const set<T>& v) {
  for (auto el : v) cout << el << " ";
  return os;
}
template <typename T, typename S>
inline ostream& operator<<(ostream& os, const map<T, S>& v) {
  for (auto el : v) cout << el << " ";
  return os;
}
template <typename T>
inline ostream& operator<<(ostream& os, const multiset<T>& v) {
  for (auto el : v) cout << el << " ";
  return os;
}
namespace ___debug {
struct DebugStream {
 private:
  bool is_first;

 public:
  DebugStream(bool _is_first) : is_first(_is_first) {}
  template <typename T>
  DebugStream operator<<(const T& value) const {
    assert(0);
    if (is_first) cout << "[DBG] ";
    cout << value;
    return DebugStream(false);
  };
  template <typename T>
  DebugStream printArray(T* l, T* r) {
    assert(0);
    if (is_first) cout << "[DBG] ";
    while (l != r) {
      cout << (*l);
      ++l;
      if (l == r) {
        cout << '\n';
      } else {
        cout << ' ';
      }
    }
    return DebugStream(false);
  }
};
DebugStream instance(true);
};  // namespace ___debug
const int INT_INF = (int)(2e9);
const ll LL_INF = (ll)(2e18);
const int NIL = -1;
static mt19937 _g(time(nullptr));
inline ll randint(ll a, ll b) {
  ll w = (_g() << 31LL) ^ _g();
  return a + w % (b - a + 1);
}
inline void fast_io() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
};
template <typename T>
inline T sign(T x) {
  return T(x > 0) - T(x < 0);
}
template <typename T>
inline T fetch() {
  T ret;
  cin >> ret;
  return ret;
}
template <typename T>
inline vector<T> fetch_vec(int sz) {
  vector<T> ret(sz);
  for (auto& elem : ret) cin >> elem;
  return ret;
}
int GCD(int x, int y) { return x ? GCD(y % x, x) : y; }
const int MAXN = (int)2e5 + 77;
int a[2 * MAXN], b[2 * MAXN], n;
int pref[MAXN], mx[MAXN], gcdWithN[MAXN];
void solve() {
  cin >> n;
  for (int i = 0; i <= n; ++i) gcdWithN[i] = GCD(i, n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = n; i < 2 * n; ++i) a[i] = a[i - n];
  ll answ = 0;
  for (int g = 1; g < n; ++g)
    if (n % g == 0) {
      42;
      ;
      pref[0] = 0;
      for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + (gcdWithN[i] == g);
      for (int i = 0; i < g; ++i) mx[i] = 0;
      int ptr = 0;
      for (int i = 0; i < n; ++i) {
        mx[ptr] = max(mx[ptr], a[i]);
        ++ptr;
        if (ptr >= g) ptr -= g;
      }
      ptr = 0;
      for (int i = 0; i < 2 * n; ++i) {
        b[i] = mx[ptr];
        ++ptr;
        if (ptr >= g) ptr -= g;
      }
      int sz = 0;
      for (int i = 0; i < n; ++i) {
        while (sz < n && b[i + sz] <= a[i + sz]) ++sz;
        if (sz) {
          answ += pref[sz];
          --sz;
        }
      }
    }
  cout << answ << '\n';
}
int main() {
  fast_io();
  solve();
  return 0;
}
