#include <bits/stdc++.h>
using namespace std;
const int M = 1000000007;
const int MM = 998244353;
const long double PI = acos(-1);
long long power(long long b, long long e, long long m) {
  if (e == 0) return 1;
  if (e & 1) return b * power(b * b % m, e / 2, m) % m;
  return power(b * b % m, e / 2, m);
}
long long power(long long b, long long e) {
  if (e == 0) return 1;
  if (e & 1) return b * power(b * b, e / 2);
  return power(b * b, e / 2);
}
template <typename T, typename U>
static inline void amin(T &x, U y) {
  if (y < x) x = y;
}
template <typename T, typename U>
static inline void amax(T &x, U y) {
  if (x < y) x = y;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  return os << '(' << p.first << "," << p.second << ')';
}
const int N = 300005;
int a[N];
int pos[N];
int last[N];
struct node {
  long long minimum, cnt;
} fake{2000000000000000000, 0ll};
struct SEGTREE {
  long long a[N];
  SEGTREE() { memset(a, 0, sizeof(a)); }
  node tree[4 * N];
  long long lazy[4 * N];
  inline node combine(node a, node b) {
    node ret;
    ret.minimum = min(a.minimum, b.minimum);
    ret.cnt = 0;
    if (ret.minimum == a.minimum) ret.cnt += a.cnt;
    if (ret.minimum == b.minimum) ret.cnt += b.cnt;
    return ret;
  }
  inline node make_node(long long val) {
    node ret;
    ret.minimum = val;
    ret.cnt = 1;
    return ret;
  }
  inline void pushdown(long long v, long long st, long long en) {
    tree[v].minimum += lazy[v];
    if (st != en) {
      lazy[v << 1] += lazy[v];
      lazy[v << 1 | 1] += lazy[v];
    }
    lazy[v] = 0;
    return;
  }
  void buildTree(long long v, long long st, long long en) {
    if (st == en) {
      tree[v] = make_node(a[st]);
      return;
    }
    long long mid = (st + en) >> 1;
    buildTree(v << 1, st, mid);
    buildTree(v << 1 | 1, mid + 1, en);
    tree[v] = combine(tree[v << 1], tree[v << 1 | 1]);
  }
  void update(long long v, long long st, long long en, long long in,
              long long val) {
    long long mid = (st + en) >> 1;
    if (st == en) {
      tree[v] = make_node(val);
      a[st] = val;
      return;
    }
    if (in <= mid)
      update(v << 1, st, mid, in, val);
    else
      update(v << 1 | 1, mid + 1, en, in, val);
    tree[v] = combine(tree[v << 1], tree[v << 1 | 1]);
  }
  void rupdate(long long v, long long st, long long en, long long l,
               long long r, long long val) {
    if (lazy[v] != 0) {
      pushdown(v, st, en);
    }
    if (en < l || st > r) return;
    if (st >= l && en <= r) {
      lazy[v] = val;
      pushdown(v, st, en);
      return;
    }
    long long mid = (st + en) >> 1;
    rupdate(v << 1, st, mid, l, r, val);
    rupdate(v << 1 | 1, mid + 1, en, l, r, val);
    tree[v] = combine(tree[v << 1], tree[v << 1 | 1]);
  }
  node query(long long v, long long st, long long en, long long l,
             long long r) {
    if (en < l || st > r) return fake;
    if (lazy[v] != 0) {
      pushdown(v, st, en);
    }
    if (st >= l && en <= r) return tree[v];
    long long mid = (st + en) >> 1;
    return combine(query(v << 1, st, mid, l, r),
                   query(v << 1 | 1, mid + 1, en, l, r));
  }
} seg;
int _runtimeTerror_() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    pos[i] = -1;
    last[i] = -1;
  }
  for (int i = 1; i <= n; ++i) seg.a[i] = 0;
  seg.buildTree(1, 1, n);
  stack<int> st;
  st.push(0);
  int z_pos = 0;
  long long ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (last[a[i]] != -1) amax(z_pos, last[a[i]]);
    last[a[i]] = i;
    pos[a[i]] = i;
    while (st.top() != 0 && a[st.top()] < a[i]) {
      int x = st.top();
      st.pop();
      seg.rupdate(1, 1, n, st.top() + 1, x, a[i] - a[x]);
    }
    st.push(i);
    seg.rupdate(1, 1, n, i, i, a[i]);
    seg.rupdate(1, 1, n, 1, i, -1);
    if (pos[1] == -1 || pos[1] < z_pos) continue;
    node u = seg.query(1, 1, n, z_pos + 1, pos[1]);
    if (u.minimum == 0) ans += u.cnt;
  }
  cout << ans << "\n";
  return 0;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int TESTS = 1;
  while (TESTS--) _runtimeTerror_();
  return 0;
}

### Prompt

Please formulate a CPP solution to the following problem:

You have an array a_1, a_2, ..., a_n. 

Let's call some subarray a_l, a_{l + 1}, ... , a_r of this array a subpermutation if it contains all integers from 1 to r-l+1 exactly once. For example, array a = [2, 2, 1, 3, 2, 3, 1] contains 6 subarrays which are subpermutations: [a_2 ... a_3], [a_2 ... a_4], [a_3 ... a_3], [a_3 ... a_5], [a_5 ... a_7], [a_7 ... a_7].

You are asked to calculate the number of subpermutations.

Input

The first line contains one integer n (1 ≤ n ≤ 3 ⋅ 10^5).

The second line contains n integers a_1, a_2, ... , a_n (1 ≤ a_i ≤ n). 

This array can contain the same integers.

Output

Print the number of subpermutations of the array a.

Examples

Input


8
2 4 1 3 4 2 1 2


Output


7


Input


5
1 1 2 1 2


Output


6

Note

There are 7 subpermutations in the first test case. Their segments of indices are [1, 4], [3, 3], [3, 6], [4, 7], [6, 7], [7, 7] and [7, 8].

In the second test case 6 subpermutations exist: [1, 1], [2, 2], [2, 3], [3, 4], [4, 4] and [4, 5].

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int M = 1000000007;
const int MM = 998244353;
const long double PI = acos(-1);
long long power(long long b, long long e, long long m) {
  if (e == 0) return 1;
  if (e & 1) return b * power(b * b % m, e / 2, m) % m;
  return power(b * b % m, e / 2, m);
}
long long power(long long b, long long e) {
  if (e == 0) return 1;
  if (e & 1) return b * power(b * b, e / 2);
  return power(b * b, e / 2);
}
template <typename T, typename U>
static inline void amin(T &x, U y) {
  if (y < x) x = y;
}
template <typename T, typename U>
static inline void amax(T &x, U y) {
  if (x < y) x = y;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  return os << '(' << p.first << "," << p.second << ')';
}
const int N = 300005;
int a[N];
int pos[N];
int last[N];
struct node {
  long long minimum, cnt;
} fake{2000000000000000000, 0ll};
struct SEGTREE {
  long long a[N];
  SEGTREE() { memset(a, 0, sizeof(a)); }
  node tree[4 * N];
  long long lazy[4 * N];
  inline node combine(node a, node b) {
    node ret;
    ret.minimum = min(a.minimum, b.minimum);
    ret.cnt = 0;
    if (ret.minimum == a.minimum) ret.cnt += a.cnt;
    if (ret.minimum == b.minimum) ret.cnt += b.cnt;
    return ret;
  }
  inline node make_node(long long val) {
    node ret;
    ret.minimum = val;
    ret.cnt = 1;
    return ret;
  }
  inline void pushdown(long long v, long long st, long long en) {
    tree[v].minimum += lazy[v];
    if (st != en) {
      lazy[v << 1] += lazy[v];
      lazy[v << 1 | 1] += lazy[v];
    }
    lazy[v] = 0;
    return;
  }
  void buildTree(long long v, long long st, long long en) {
    if (st == en) {
      tree[v] = make_node(a[st]);
      return;
    }
    long long mid = (st + en) >> 1;
    buildTree(v << 1, st, mid);
    buildTree(v << 1 | 1, mid + 1, en);
    tree[v] = combine(tree[v << 1], tree[v << 1 | 1]);
  }
  void update(long long v, long long st, long long en, long long in,
              long long val) {
    long long mid = (st + en) >> 1;
    if (st == en) {
      tree[v] = make_node(val);
      a[st] = val;
      return;
    }
    if (in <= mid)
      update(v << 1, st, mid, in, val);
    else
      update(v << 1 | 1, mid + 1, en, in, val);
    tree[v] = combine(tree[v << 1], tree[v << 1 | 1]);
  }
  void rupdate(long long v, long long st, long long en, long long l,
               long long r, long long val) {
    if (lazy[v] != 0) {
      pushdown(v, st, en);
    }
    if (en < l || st > r) return;
    if (st >= l && en <= r) {
      lazy[v] = val;
      pushdown(v, st, en);
      return;
    }
    long long mid = (st + en) >> 1;
    rupdate(v << 1, st, mid, l, r, val);
    rupdate(v << 1 | 1, mid + 1, en, l, r, val);
    tree[v] = combine(tree[v << 1], tree[v << 1 | 1]);
  }
  node query(long long v, long long st, long long en, long long l,
             long long r) {
    if (en < l || st > r) return fake;
    if (lazy[v] != 0) {
      pushdown(v, st, en);
    }
    if (st >= l && en <= r) return tree[v];
    long long mid = (st + en) >> 1;
    return combine(query(v << 1, st, mid, l, r),
                   query(v << 1 | 1, mid + 1, en, l, r));
  }
} seg;
int _runtimeTerror_() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    pos[i] = -1;
    last[i] = -1;
  }
  for (int i = 1; i <= n; ++i) seg.a[i] = 0;
  seg.buildTree(1, 1, n);
  stack<int> st;
  st.push(0);
  int z_pos = 0;
  long long ans = 0;
  for (int i = 1; i <= n; ++i) {
    if (last[a[i]] != -1) amax(z_pos, last[a[i]]);
    last[a[i]] = i;
    pos[a[i]] = i;
    while (st.top() != 0 && a[st.top()] < a[i]) {
      int x = st.top();
      st.pop();
      seg.rupdate(1, 1, n, st.top() + 1, x, a[i] - a[x]);
    }
    st.push(i);
    seg.rupdate(1, 1, n, i, i, a[i]);
    seg.rupdate(1, 1, n, 1, i, -1);
    if (pos[1] == -1 || pos[1] < z_pos) continue;
    node u = seg.query(1, 1, n, z_pos + 1, pos[1]);
    if (u.minimum == 0) ans += u.cnt;
  }
  cout << ans << "\n";
  return 0;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int TESTS = 1;
  while (TESTS--) _runtimeTerror_();
  return 0;
}

```