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;
const int Inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3fll;
int n, p[200005];
struct Segbeats {
  int mx[1 << 20], nx[1 << 20], mn[1 << 20], nn[1 << 20];
  int cmx[1 << 20], cmn[1 << 20], tag[1 << 20];
  long long sm[1 << 20];
  void inline pu(int now) {
    sm[now] = sm[now << 1] + sm[now << 1 | 1];
    if (mx[(now << 1)] > mx[(now << 1 | 1)]) {
      mx[now] = mx[(now << 1)];
      cmx[now] = cmx[(now << 1)];
      nx[now] = max(nx[(now << 1)], mx[(now << 1 | 1)]);
    } else if (mx[(now << 1)] < mx[(now << 1 | 1)]) {
      mx[now] = mx[(now << 1 | 1)];
      cmx[now] = cmx[(now << 1 | 1)];
      nx[now] = max(mx[(now << 1)], nx[(now << 1 | 1)]);
    } else {
      mx[now] = mx[(now << 1)];
      cmx[now] = cmx[(now << 1)] + cmx[(now << 1 | 1)];
      nx[now] = max(nx[(now << 1)], nx[(now << 1 | 1)]);
    }
    if (mn[(now << 1)] < mn[(now << 1 | 1)]) {
      mn[now] = mn[(now << 1)];
      cmn[now] = cmn[(now << 1)];
      nn[now] = min(nn[(now << 1)], mn[(now << 1 | 1)]);
    } else if (mn[(now << 1)] > mn[(now << 1 | 1)]) {
      mn[now] = mn[(now << 1 | 1)];
      cmn[now] = cmn[(now << 1 | 1)];
      nn[now] = min(mn[(now << 1)], nn[(now << 1 | 1)]);
    } else {
      mn[now] = mn[(now << 1)];
      cmn[now] = cmn[(now << 1)] + cmn[(now << 1 | 1)];
      nn[now] = min(nn[(now << 1)], nn[(now << 1 | 1)]);
    }
  }
  void inline init(int x, int now = 1, int nl = 1, int nr = n) {
    if (nl == nr) {
      mx[now] = mn[now] = x;
      cmx[now] = cmn[now] = 1;
      nx[now] = -Inf;
      nn[now] = Inf;
      tag[now] = 0;
      sm[now] = x;
      return;
    }
    int m = (nl + nr) >> 1;
    init(x, (now << 1), nl, m);
    init(x, (now << 1 | 1), m + 1, nr);
    pu(now);
  }
  void inline ptag(int now, int nl, int nr, int val) {
    tag[now] += val;
    sm[now] += 1ll * val * (nr - nl + 1);
    mx[now] += val;
    mn[now] += val;
    nx[now] += val;
    nn[now] += val;
  }
  void inline pmax(int now, int nl, int nr, int val) {
    sm[now] += 1ll * cmn[now] * (val - mn[now]);
    mn[now] = val;
    mx[now] = max(mx[now], val);
    if (mn[now] == mx[now]) {
      sm[now] = 1ll * (nr - nl + 1) * val;
      cmn[now] = cmx[now] = nr - nl + 1;
      nn[now] = Inf;
      nx[now] = -Inf;
    } else {
      nn[now] = max(nn[now], val);
    }
  }
  void inline pmin(int now, int nl, int nr, int val) {
    sm[now] += 1ll * cmx[now] * (val - mx[now]);
    mx[now] = val;
    mn[now] = min(mn[now], val);
    if (mn[now] == mx[now]) {
      sm[now] = 1ll * (nr - nl + 1) * val;
      cmn[now] = cmx[now] = nr - nl + 1;
      nn[now] = Inf;
      nx[now] = -Inf;
    } else {
      nx[now] = min(nx[now], val);
    }
  }
  void inline pd(int now, int nl, int nr) {
    int m = (nl + nr) >> 1;
    if (tag[now]) {
      ptag((now << 1), nl, m, tag[now]);
      ptag((now << 1 | 1), m + 1, nr, tag[now]);
      tag[now] = 0;
    }
    if (mx[(now << 1)] > mx[now]) pmin((now << 1), nl, m, mx[now]);
    if (mx[(now << 1 | 1)] > mx[now]) pmin((now << 1 | 1), m + 1, nr, mx[now]);
    if (mn[(now << 1)] < mn[now]) pmax((now << 1), nl, m, mn[now]);
    if (mn[(now << 1 | 1)] < mn[now]) pmax((now << 1 | 1), m + 1, nr, mn[now]);
  }
  void add(int l, int r, int x, int now = 1, int nl = 1, int nr = n) {
    if (l > r || nl > r || nr < l) return;
    if (nl >= l && nr <= r) return ptag(now, nl, nr, x);
    int m = (nl + nr) >> 1;
    pd(now, nl, nr);
    add(l, r, x, (now << 1), nl, m);
    add(l, r, x, (now << 1 | 1), m + 1, nr);
    pu(now);
  }
  void qmin(int l, int r, int x, int now = 1, int nl = 1, int nr = n) {
    if (l > r || nl > r || nr < l) return;
    if (mx[now] <= x) return;
    if (nl >= l && nr <= r) {
      if (nx[now] < x) return pmin(now, nl, nr, x);
    }
    int m = (nl + nr) >> 1;
    pd(now, nl, nr);
    qmin(l, r, x, (now << 1), nl, m);
    qmin(l, r, x, (now << 1 | 1), m + 1, nr);
    pu(now);
  }
  void qmax(int l, int r, int x, int now = 1, int nl = 1, int nr = n) {
    if (l > r || nl > r || nr < l) return;
    if (mn[now] >= x) return;
    if (nl >= l && nr <= r) {
      if (nn[now] > x) return pmax(now, nl, nr, x);
    }
    int m = (nl + nr) >> 1;
    pd(now, nl, nr);
    qmax(l, r, x, (now << 1), nl, m);
    qmax(l, r, x, (now << 1 | 1), m + 1, nr);
    pu(now);
  }
  int get(int to, int now = 1, int nl = 1, int nr = n) {
    if (nl == nr) return sm[now];
    int m = (nl + nr) >> 1;
    pd(now, nl, nr);
    if (m >= to)
      return get(to, (now << 1), nl, m);
    else
      return get(to, (now << 1 | 1), m + 1, nr);
  }
} sl, sr;
struct Fenwick {
  int dt[200005];
  void inline add(int a, int x) {
    for (; a <= n; a += a & -a) dt[a] += x;
  }
  int inline sum(int a) {
    int res = 0;
    for (; a; a -= a & -a) res += dt[a];
    return res;
  }
  int inline sum(int l, int r) { return sum(r) - sum(l - 1); }
} bit;
int q[200005];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= (n); ++i) scanf("%d", p + i), q[p[i]] = i;
  sl.init(1);
  sr.init(0);
  for (int i = 1; i <= (n); ++i) {
    int pos = q[i];
    int id = bit.sum(1, pos);
    bit.add(pos, 1);
    sr.qmin(1, pos, id);
    sl.qmax(pos, n, id + 1);
    sl.add(pos + 1, n, 1);
    sr.add(pos + 1, n, 1);
    sl.add(pos, pos, 1 - sl.get(pos));
    sr.add(pos, pos, i - sr.get(pos));
    printf("%lld\n", sr.sm[1] - sl.sm[1] + n);
  }
  return 0;
}
