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>
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  if (flag) x = -x;
}
using namespace std;
const int inf = 987654321;
int n;
int a[151000], pos[151000];
namespace BIT {
int tre[151000];
inline void add(int i, int x) {
  while (i <= n) tre[i] += x, i += ((i) & (-(i)));
}
inline int query(int i) {
  int res = 0;
  while (i) res += tre[i], i -= ((i) & (-(i)));
  return res;
}
}  // namespace BIT
namespace Seg_R {
struct Data {
  int ls, rs, cnt, mx, mxcnt, smx, mintag, addtag;
  long long sum;
  Data() {
    ls = rs = cnt = mxcnt = sum = addtag = 0;
    mx = smx = mintag = -1;
  }
} Dat[151000 << 2];
int ttot;
inline void pushup(int cur) {
  Dat[cur].sum = Dat[Dat[cur].ls].sum + Dat[Dat[cur].rs].sum;
  Dat[cur].cnt = Dat[Dat[cur].ls].cnt + Dat[Dat[cur].rs].cnt;
  if (Dat[Dat[cur].ls].mx == Dat[Dat[cur].rs].mx) {
    Dat[cur].mx = Dat[Dat[cur].ls].mx;
    Dat[cur].mxcnt = Dat[Dat[cur].ls].mxcnt + Dat[Dat[cur].rs].mxcnt;
    Dat[cur].smx = max(Dat[Dat[cur].ls].smx, Dat[Dat[cur].rs].smx);
  } else if (Dat[Dat[cur].ls].mx > Dat[Dat[cur].rs].mx) {
    Dat[cur].mx = Dat[Dat[cur].ls].mx, Dat[cur].mxcnt = Dat[Dat[cur].ls].mxcnt;
    Dat[cur].smx = max(Dat[Dat[cur].ls].smx, Dat[Dat[cur].rs].mx);
  } else {
    Dat[cur].mx = Dat[Dat[cur].rs].mx, Dat[cur].mxcnt = Dat[Dat[cur].rs].mxcnt;
    Dat[cur].smx = max(Dat[Dat[cur].rs].smx, Dat[Dat[cur].ls].mx);
  }
}
inline void pushadd(int cur, int v) {
  if (!Dat[cur].cnt) return;
  Dat[cur].sum += 1ll * Dat[cur].cnt * v;
  Dat[cur].mx += v;
  Dat[cur].smx += v;
  Dat[cur].addtag += v;
  if (~Dat[cur].mintag) Dat[cur].mintag += v;
}
inline void pushmin(int cur, int v) {
  if (!Dat[cur].cnt || Dat[cur].mx <= v) return;
  Dat[cur].sum += 1ll * Dat[cur].mxcnt * (v - Dat[cur].mx);
  Dat[cur].mx = v;
  Dat[cur].mintag = v;
}
inline void pushdown(int cur) {
  if (Dat[cur].addtag)
    pushadd(Dat[cur].ls, Dat[cur].addtag),
        pushadd(Dat[cur].rs, Dat[cur].addtag), Dat[cur].addtag = 0;
  if (~Dat[cur].mintag)
    pushmin(Dat[cur].ls, Dat[cur].mintag),
        pushmin(Dat[cur].rs, Dat[cur].mintag), Dat[cur].mintag = -1;
}
void modify_min(int L, int R, int l, int r, int v, int cur) {
  if (!cur || Dat[cur].mx <= v) return;
  if (l <= L && R <= r && Dat[cur].smx < v) return pushmin(cur, v), void();
  int mid = (L + R) >> 1;
  pushdown(cur);
  if (l <= mid) modify_min(L, mid, l, r, v, Dat[cur].ls);
  if (r > mid) modify_min(mid + 1, R, l, r, v, Dat[cur].rs);
  pushup(cur);
}
void modify_add(int L, int R, int l, int r, int v, int cur) {
  if (!cur) return;
  if (l <= L && R <= r) return pushadd(cur, v), void();
  int mid = (L + R) >> 1;
  pushdown(cur);
  if (l <= mid) modify_add(L, mid, l, r, v, Dat[cur].ls);
  if (r > mid) modify_add(mid + 1, R, l, r, v, Dat[cur].rs);
  pushup(cur);
}
void modify_point(int L, int R, int pos, int v, int &cur) {
  if (!cur) cur = ++ttot;
  if (L == R)
    return Dat[cur].sum = Dat[cur].mx = v, Dat[cur].mxcnt = 1, Dat[cur].cnt = 1,
           void();
  int mid = (L + R) >> 1;
  pushdown(cur);
  if (pos <= mid)
    modify_point(L, mid, pos, v, Dat[cur].ls);
  else
    modify_point(mid + 1, R, pos, v, Dat[cur].rs);
  pushup(cur);
}
}  // namespace Seg_R
namespace Seg_L {
struct Data {
  int ls, rs, cnt, mn, mncnt, smn, maxtag, addtag;
  long long sum;
  Data() {
    ls = rs = cnt = mncnt = sum = addtag = 0;
    mn = smn = maxtag = inf;
  }
} Dat[151000 << 2];
int ttot;
inline void pushup(int cur) {
  Dat[cur].sum = Dat[Dat[cur].ls].sum + Dat[Dat[cur].rs].sum;
  Dat[cur].cnt = Dat[Dat[cur].ls].cnt + Dat[Dat[cur].rs].cnt;
  if (Dat[Dat[cur].ls].mn == Dat[Dat[cur].rs].mn) {
    Dat[cur].mn = Dat[Dat[cur].ls].mn;
    Dat[cur].mncnt = Dat[Dat[cur].ls].mncnt + Dat[Dat[cur].rs].mncnt;
    Dat[cur].smn = min(Dat[Dat[cur].ls].smn, Dat[Dat[cur].rs].smn);
  } else if (Dat[Dat[cur].ls].mn < Dat[Dat[cur].rs].mn) {
    Dat[cur].mn = Dat[Dat[cur].ls].mn, Dat[cur].mncnt = Dat[Dat[cur].ls].mncnt;
    Dat[cur].smn = min(Dat[Dat[cur].ls].smn, Dat[Dat[cur].rs].mn);
  } else {
    Dat[cur].mn = Dat[Dat[cur].rs].mn, Dat[cur].mncnt = Dat[Dat[cur].rs].mncnt;
    Dat[cur].smn = min(Dat[Dat[cur].rs].smn, Dat[Dat[cur].ls].mn);
  }
}
inline void pushadd(int cur, int v) {
  if (!Dat[cur].cnt) return;
  Dat[cur].sum += 1ll * Dat[cur].cnt * v;
  Dat[cur].mn += v;
  Dat[cur].smn += v;
  Dat[cur].addtag += v;
  if (Dat[cur].maxtag != inf) Dat[cur].maxtag += v;
}
inline void pushmax(int cur, int v) {
  if (!Dat[cur].cnt || Dat[cur].mn >= v) return;
  Dat[cur].sum += 1ll * Dat[cur].mncnt * (v - Dat[cur].mn);
  Dat[cur].mn = v;
  Dat[cur].maxtag = v;
}
inline void pushdown(int cur) {
  if (Dat[cur].addtag)
    pushadd(Dat[cur].ls, Dat[cur].addtag),
        pushadd(Dat[cur].rs, Dat[cur].addtag), Dat[cur].addtag = 0;
  if (Dat[cur].maxtag != inf)
    pushmax(Dat[cur].ls, Dat[cur].maxtag),
        pushmax(Dat[cur].rs, Dat[cur].maxtag), Dat[cur].maxtag = inf;
}
void modify_max(int L, int R, int l, int r, int v, int cur) {
  if (!cur || Dat[cur].mn >= v) return;
  if (l <= L && R <= r && Dat[cur].smn > v) return pushmax(cur, v), void();
  int mid = (L + R) >> 1;
  pushdown(cur);
  if (l <= mid) modify_max(L, mid, l, r, v, Dat[cur].ls);
  if (r > mid) modify_max(mid + 1, R, l, r, v, Dat[cur].rs);
  pushup(cur);
}
void modify_add(int L, int R, int l, int r, int v, int cur) {
  if (!cur) return;
  if (l <= L && R <= r) return pushadd(cur, v), void();
  int mid = (L + R) >> 1;
  pushdown(cur);
  if (l <= mid) modify_add(L, mid, l, r, v, Dat[cur].ls);
  if (r > mid) modify_add(mid + 1, R, l, r, v, Dat[cur].rs);
  pushup(cur);
}
void modify_point(int L, int R, int pos, int v, int &cur) {
  if (!cur) cur = ++ttot;
  if (L == R)
    return Dat[cur].sum = Dat[cur].mn = v, Dat[cur].mncnt = 1, Dat[cur].cnt = 1,
           void();
  int mid = (L + R) >> 1;
  pushdown(cur);
  if (pos <= mid)
    modify_point(L, mid, pos, v, Dat[cur].ls);
  else
    modify_point(mid + 1, R, pos, v, Dat[cur].rs);
  pushup(cur);
}
}  // namespace Seg_L
int main() {
  read(n);
  for (int i = 1; i <= n; ++i) read(a[i]), pos[a[i]] = i;
  int jzproot_L = 0, jzproot_R = 0;
  for (int i = 1; i <= n; ++i) {
    int rk = BIT::query(pos[i]) + 1;
    BIT::add(pos[i], 1);
    if (pos[i] > 1) Seg_R::modify_min(1, n, 1, pos[i] - 1, rk - 1, jzproot_R);
    if (pos[i] < n) {
      Seg_R::modify_add(1, n, pos[i] + 1, n, 1, jzproot_R);
      Seg_L::modify_add(1, n, pos[i] + 1, n, 1, jzproot_L);
      Seg_L::modify_max(1, n, pos[i] + 1, n, rk + 1, jzproot_L);
    }
    Seg_L::modify_point(1, n, pos[i], 1, jzproot_L);
    Seg_R::modify_point(1, n, pos[i], i, jzproot_R);
    long long res = Seg_R::Dat[1].sum - Seg_L::Dat[1].sum + i;
    printf("%lld\n", res);
  }
  return 0;
}
