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;
int a[200010], p[200010];
long long ans[200010];
set<int> S;
struct LCT {
  int ch[200010][2], fa[200010];
  int val[200010], sz[200010], ss[200010], sss[200010];
  long long sum[200010], ssum[200010];
  LCT() {
    memset(ch, 0, sizeof(ch)), memset(fa, 0, sizeof(fa)),
        memset(sz, 0, sizeof(sz));
    memset(sss, 0, sizeof(sss)), memset(ss, 0, sizeof(ss)),
        memset(sum, 0, sizeof(sum));
    memset(ssum, 0, sizeof(ssum));
  }
  void pushup(int x) {
    sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
    ss[x] = ss[ch[x][0]] + ss[ch[x][1]] + sss[x] + 1;
    sum[x] = ssum[x] + sum[ch[x][0]] + sum[ch[x][1]];
    sum[x] += 1ll * (sz[ch[x][0]] + 1) * (ss[ch[x][1]] + sss[x] + 1);
  }
  void rotate(int x) {
    int p = fa[x], d = ((x) == ch[fa[x]][1]);
    ch[p][d] = ch[x][d ^ 1], fa[ch[x][d ^ 1]] = p;
    if (!(ch[fa[p]][0] != (p) && ch[fa[p]][1] != (p)))
      ch[fa[p]][((p) == ch[fa[p]][1])] = x;
    fa[x] = fa[p];
    ch[x][d ^ 1] = p, fa[p] = x;
    pushup(p), pushup(x);
  }
  void splay(int x) {
    while (!(ch[fa[x]][0] != (x) && ch[fa[x]][1] != (x))) {
      int p = fa[x];
      if (!(ch[fa[p]][0] != (p) && ch[fa[p]][1] != (p)))
        rotate(((x) == ch[fa[x]][1]) == ((p) == ch[fa[p]][1]) ? p : x);
      rotate(x);
    }
    pushup(x);
  }
  void access(int x) {
    int lst = 0;
    while (x) {
      splay(x);
      sss[x] += ss[ch[x][1]] - ss[lst], ssum[x] += sum[ch[x][1]] - sum[lst];
      ch[x][1] = lst, pushup(x);
      lst = x, x = fa[x];
    }
  }
  int Insert(int x, int y) {
    while (1) {
      int to = y > x ? 0 : 1;
      if (!ch[x][to]) {
        ch[x][to] = y, fa[y] = x, pushup(x);
        while (!(ch[fa[x]][0] != (x) && ch[fa[x]][1] != (x)))
          x = fa[x], pushup(x);
        break;
      }
      x = ch[x][to];
    }
    splay(y);
    return y;
  }
  int Merge(int x, int y) {
    if (!y) return x;
    int ls = ch[y][0], rs = ch[y][1];
    fa[ls] = fa[rs] = 0, ch[y][0] = ch[y][1] = 0, pushup(y);
    x = Insert(x, y), x = Merge(x, ls), x = Merge(x, rs);
    return x;
  }
} lct;
struct RMQ {
  int a[200010], f[200010][18], lg[200010];
  int MAX(int x, int y) { return a[x] < a[y] ? y : x; }
  void init(int *A, int n) {
    lg[0] = -1;
    for (int i = 1; i <= n; i++) {
      f[i][0] = i, a[i] = A[i], lg[i] = lg[i >> 1] + 1;
    }
    for (int j = 1; j < 18; j++) {
      for (int i = 1; i <= n; i++) {
        if (i + (1 << j) - 1 > n) break;
        f[i][j] = MAX(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
      }
    }
  }
  int get_max(int l, int r) {
    int k = lg[r - l + 1];
    return MAX(f[l][k], f[r - (1 << k) + 1][k]);
  }
} rmq;
int Build(int l, int r) {
  if (l > r) return 0;
  int mid = rmq.get_max(l, r), x = a[mid];
  int ls = Build(l, mid - 1), rs = Build(mid + 1, r);
  lct.fa[ls] = x, lct.fa[rs] = x;
  lct.sss[x] = r - l, lct.ssum[x] = lct.sum[ls] + lct.sum[rs];
  lct.pushup(x);
  return x;
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    p[a[i]] = i;
    S.insert(i);
  }
  rmq.init(a, n);
  Build(1, n);
  ans[n] = lct.sum[n];
  for (int i = n; i >= 2; i--) {
    S.erase(p[i]);
    set<int>::iterator it = S.lower_bound(p[i]);
    int suc = it == S.end() ? 0 : a[*it],
        pre = it == S.begin() ? 0 : a[*(--it)];
    if (pre)
      lct.access(pre), lct.splay(pre), lct.splay(i), lct.fa[lct.ch[i][1]] = 0,
                                                     lct.splay(pre);
    if (suc)
      lct.access(suc), lct.splay(suc), lct.splay(i), lct.fa[lct.ch[i][1]] = 0,
                                                     lct.splay(suc);
    if (lct.sz[pre] < lct.sz[suc]) swap(pre, suc);
    lct.Merge(pre, suc);
    lct.splay(i - 1), ans[i - 1] = lct.sum[i - 1];
  }
  for (int i = 1; i <= n; i++) {
    printf("%lld ", ans[i]);
  }
  printf("\n");
  return 0;
}
