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 N = 500005;
struct node {
  int ch[2], fa, s, lv, rv, s1, s2, ov;
  char f;
  long long tot;
  inline bool lr(const int& x) { return ch[1] == x; }
} t[N];
int son[N][2], tcnt;
inline bool isroot(int x) {
  return t[t[x].fa].ch[0] != x && t[t[x].fa].ch[1] != x;
}
inline char calc(const int& x, const int& y) {
  return x && y ? (x > y ? 1 : 2) : 0;
}
inline void maintain(int x) {
  int l = t[x].ch[0], r = t[x].ch[1];
  t[x].f = t[l].f | t[r].f | calc(t[l].rv, x) | calc(x, t[r].lv);
  t[x].lv = l ? t[l].lv : x;
  t[x].rv = r ? t[r].rv : x;
  t[x].s = t[l].s + t[r].s + t[x].ov;
  t[x].s1 = t[l].s1 + t[r].s1 + t[son[x][0]].s1 + t[son[x][1]].s1 + t[x].ov;
  t[x].s2 = t[l].s2 + t[r].s2 + t[son[x][0]].s1 + t[x].ov;
  t[x].tot = t[r].tot + t[l].tot + t[son[x][0]].tot + t[son[x][1]].tot +
             1ll * (t[l].s + t[x].ov) * (t[x].s1 - t[l].s1);
}
inline void rotate(int x) {
  int y = t[x].fa, z = t[y].fa, o;
  if (!isroot(y)) t[z].ch[t[z].lr(y)] = x;
  t[x].fa = z;
  t[y].fa = x;
  o = t[y].lr(x);
  t[y].ch[o] = t[x].ch[!o];
  t[t[x].ch[!o]].fa = y;
  t[x].ch[!o] = y;
  maintain(y);
}
inline void splay(int x) {
  for (; !isroot(x); rotate(x)) {
    int y = t[x].fa, z = t[y].fa;
    if (!isroot(y)) rotate(t[z].lr(y) == t[y].lr(x) ? y : x);
  }
  maintain(x);
}
inline void access(int x) {
  for (int y = 0, z; x;) {
    splay(x);
    if (z = t[x].ch[1]) son[x][calc(x, t[z].lv) - 1] = z;
    t[x].ch[1] = y;
    if (y) son[x][calc(x, t[y].lv) - 1] = 0;
    maintain(x);
    y = x;
    x = t[x].fa;
  }
}
int n, m, i, x, y, o, rt;
inline void spaly(int x, int yy) {
  access(x);
  splay(yy);
  t[yy].ch[1] = 0;
  splay(x);
  son[yy][calc(yy, x) - 1] = x;
  int L = son[x][0], R = son[x][1], ox = x, y = t[x].ch[0], f, lv, nf, lf = 0;
  if (L) {
    for (; t[L].ch[0]; L = t[L].ch[0])
      ;
    splay(L);
    son[ox][0] = L;
  }
  if (R) {
    for (; t[R].ch[0]; R = t[R].ch[0])
      ;
    splay(R);
    son[ox][1] = R;
  }
  for (; y;) {
    lv = x, f = lf = calc(t[y].rv, x);
    for (;;) {
      nf = f | t[t[y].ch[1]].f | calc(y, t[y].ch[1] ? t[t[y].ch[1]].lv : lv);
      if (nf == lf) {
        nf |= calc(t[t[y].ch[0]].rv, y);
        if (nf != lf || !t[y].ch[0]) break;
        f = nf;
        lv = y;
        y = t[y].ch[0];
      } else {
        if (!t[y].ch[1]) break;
        y = t[y].ch[1];
      }
    }
    t[x].ch[0] = 0;
    splay(y);
    x = y;
    y = t[x].ch[0];
    int& z = lf == 1 ? R : L;
    if (!z)
      z = x, t[x].fa = ox, son[ox][calc(ox, x) - 1] = x;
    else
      t[x].fa = z, t[z].ch[0] = x, z = x;
  }
  for (; L && !isroot(L); L = t[L].fa) maintain(L);
  if (L) maintain(L);
  for (; R && !isroot(R); R = t[R].fa) maintain(R);
  if (R) maintain(R);
  t[ox].ov = 1;
  maintain(ox);
  maintain(yy);
}
inline int calc(int x) { return t[x].s1 - t[x].s2; }
void ini(int x) {
  if (son[x][0]) ini(son[x][0]);
  if (son[x][1]) ini(son[x][1]);
  maintain(x);
}
int a[N], ia[N];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (i = 1; i <= n; ++i) cin >> a[i], ia[a[i]] = i;
  for (i = 1; i <= n; ++i) t[i].fa = i + 1, son[t[i].fa][t[i].fa < i] = i;
  rt = n + 1;
  ini(rt);
  for (i = 1; i <= n; ++i) {
    spaly(ia[i], n + 1);
    cout << t[n + 1].tot << '\n';
  }
  return 0;
}
