Ildar is the algorithm teacher of William and Harris. Today, Ildar is teaching Cartesian Tree. However, Harris is sick, so Ildar is only teaching William.

A cartesian tree is a rooted tree, that can be constructed from a sequence of distinct integers. We build the cartesian tree as follows:

  1. If the sequence is empty, return an empty tree;
  2. Let the position of the maximum element be x;
  3. Remove element on the position x from the sequence and break it into the left part and the right part (which might be empty) (not actually removing it, just taking it away temporarily);
  4. Build cartesian tree for each part;
  5. Create a new vertex for the element, that was on the position x which will serve as the root of the new tree. Then, for the root of the left part and right part, if exists, will become the children for this vertex;
  6. Return the tree we have gotten.



For example, this is the cartesian tree for the sequence 4, 2, 7, 3, 5, 6, 1:

<image>

After teaching what the cartesian tree is, Ildar has assigned homework. He starts with an empty sequence a.

In the i-th round, he inserts an element with value i somewhere in a. Then, he asks a question: what is the sum of the sizes of the subtrees for every node in the cartesian tree for the current sequence a?

Node v is in the node u subtree if and only if v = u or v is in the subtree of one of the vertex u children. The size of the subtree of node u is the number of nodes v such that v is in the subtree of u.

Ildar will do n rounds in total. The homework is the sequence of answers to the n questions.

The next day, Ildar told Harris that he has to complete the homework as well. Harris obtained the final state of the sequence a from William. However, he has no idea how to find the answers to the n questions. Help Harris!

Input

The first line contains a single integer n (1 ≤ n ≤ 150000).

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n). It is guarenteed that each integer from 1 to n appears in the sequence exactly once.

Output

Print n lines, i-th line should contain a single integer — the answer to the i-th question.

Examples

Input


5
2 4 1 5 3


Output


1
3
6
8
11


Input


6
1 2 4 5 6 3


Output


1
3
6
8
12
17

Note

After the first round, the sequence is 1. The tree is

<image>

The answer is 1.

After the second round, the sequence is 2, 1. The tree is

<image>

The answer is 2+1=3.

After the third round, the sequence is 2, 1, 3. The tree is

<image>

The answer is 2+1+3=6.

After the fourth round, the sequence is 2, 4, 1, 3. The tree is

<image>

The answer is 1+4+1+2=8.

After the fifth round, the sequence is 2, 4, 1, 5, 3. The tree is

<image>

The answer is 1+3+1+5+1=11.
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &x) {
  int f = 0;
  x = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  if (f) x = -x;
}
const int N = 300005;
struct seg {
  int mx[N << 2], T[N << 2], c[N << 2];
  int calc(int o, int l, int r, int val) {
    if (l == r) return mx[o] > val;
    if (val < mx[(o << 1)])
      return T[o] + calc((o << 1), l, ((l + r) >> 1), val);
    return calc((o << 1 | 1), ((l + r) >> 1) + 1, r, val);
  }
  void upd(int o, int l, int r, int x, int val) {
    if (l == r) {
      mx[o] = val, c[o]++;
      return;
    }
    if (x <= ((l + r) >> 1))
      upd((o << 1), l, ((l + r) >> 1), x, val);
    else
      upd((o << 1 | 1), ((l + r) >> 1) + 1, r, x, val);
    mx[o] = max(mx[(o << 1)], mx[(o << 1 | 1)]);
    T[o] = calc((o << 1 | 1), ((l + r) >> 1) + 1, r, mx[(o << 1)]);
    c[o] = c[(o << 1)] + c[(o << 1 | 1)];
  }
  int qry(int o, int l, int r, int x, int y, int &ret) {
    if (x > y || r < x || y < l) return 0;
    if (l == x && y == r) {
      int res = calc(o, l, r, ret);
      return ret = max(ret, mx[o]), res;
    }
    if (y <= ((l + r) >> 1)) return qry((o << 1), l, ((l + r) >> 1), x, y, ret);
    if (((l + r) >> 1) < x)
      return qry((o << 1 | 1), ((l + r) >> 1) + 1, r, x, y, ret);
    int res = qry((o << 1), l, ((l + r) >> 1), x, ((l + r) >> 1), ret);
    return res +
           qry((o << 1 | 1), ((l + r) >> 1) + 1, r, ((l + r) >> 1) + 1, y, ret);
  }
  int count(int o, int l, int r, int x, int y) {
    if (x > y || r < x || y < l) return 0;
    if (l == x && y == r) return c[o];
    if (y <= ((l + r) >> 1)) return count((o << 1), l, ((l + r) >> 1), x, y);
    if (((l + r) >> 1) < x)
      return count((o << 1 | 1), ((l + r) >> 1) + 1, r, x, y);
    int res = count((o << 1), l, ((l + r) >> 1), x, ((l + r) >> 1));
    return res +
           count((o << 1 | 1), ((l + r) >> 1) + 1, r, ((l + r) >> 1) + 1, y);
  }
  int Find(int o, int l, int r, int x, int val) {
    if (x > r) return 0;
    if (x <= l && mx[o] < val) return 0;
    if (l == r) return l;
    int ret =
        (x <= ((l + r) >> 1) ? Find((o << 1), l, ((l + r) >> 1), x, val) : 0);
    return ret ? ret : Find((o << 1 | 1), ((l + r) >> 1) + 1, r, x, val);
  }
} L, R;
int a[N], p[N], n;
vector<int> pre, suf;
long long ans;
int main() {
  read(n);
  for (int i = (1); i <= (n); i++) {
    read(a[i]);
    p[a[i]] = i;
  }
  for (int i = (1); i <= (n); i++) {
    int l = p[i], r = p[i], flag = -1;
    pre.clear();
    suf.clear();
    for (;;) {
      int vl = (l == p[i] ? 1 : a[l]);
      int vr = (r == p[i] ? 1 : a[r]);
      l = n + 1 - L.Find(1, 1, n, n + 1 - l + 1, vl);
      r = R.Find(1, 1, n, r + 1, vr);
      if (!r) {
        flag = 1;
        break;
      }
      if (l == n + 1) {
        flag = 0;
        break;
      }
      pre.push_back(l), suf.push_back(r);
    }
    if (flag) {
      suf.push_back(n + 1);
      int sz = suf.size() - 1;
      for (int j = 0; j < (sz); j++) {
        int cr = R.count(1, 1, n, suf[j], suf[j + 1] - 1);
        int pos = n + 1 - L.Find(1, 1, n, n + 1 - p[i], a[suf[j]]);
        if (pos == n + 1) {
          ans -= R.count(1, 1, n, 1, p[i]);
          continue;
        }
        ans -= R.count(1, 1, n, pos + 1, p[i]);
        int tmp = a[suf[j]];
        ans -= (long long)cr * L.qry(1, 1, n, n + 1 - pos, n, tmp);
      }
    } else {
      pre.push_back(0);
      int sz = pre.size() - 1;
      for (int j = 0; j < (sz); j++) {
        int cl = R.count(1, 1, n, pre[j + 1] + 1, pre[j]);
        int pos = R.Find(1, 1, n, p[i], a[pre[j]]);
        if (pos == 0) {
          ans -= R.count(1, 1, n, p[i], n);
          continue;
        }
        ans -= R.count(1, 1, n, p[i], pos - 1);
        int tmp = a[pre[j]];
        ans -= (long long)cl * R.qry(1, 1, n, pos, n, tmp);
      }
    }
    L.upd(1, 1, n, n + 1 - p[i], i);
    R.upd(1, 1, n, p[i], i);
    printf("%lld\n", ans += i);
  }
  return 0;
}
