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 = 1e9 + 69;
const int mod = 1e9 + 7;
const int MX = 150005;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node {
  int mx, mxs, mxc;
  int mn, mns, mnc;
  int lz;
  long long sum;
  node(int val = 0) {
    mn = mx = sum = val;
    mxc = mnc = 1;
    mxs = -inf;
    mns = inf;
    lz = 0;
  }
};
node merge(node a, node b) {
  node rs;
  rs.sum = a.sum + b.sum;
  rs.mx = max(a.mx, b.mx);
  if (a.mx == b.mx) {
    rs.mxc = a.mxc + b.mxc;
    rs.mxs = max(a.mxs, b.mxs);
  } else if (a.mx > b.mx) {
    rs.mxc = a.mxc;
    rs.mxs = max(a.mxs, b.mx);
  } else {
    rs.mxc = b.mxc;
    rs.mxs = max(a.mx, b.mxs);
  }
  rs.mn = min(a.mn, b.mn);
  if (a.mn == b.mn) {
    rs.mnc = a.mnc + b.mnc;
    rs.mns = min(a.mns, b.mns);
  } else if (a.mn < b.mn) {
    rs.mnc = a.mnc;
    rs.mns = min(a.mns, b.mn);
  } else {
    rs.mnc = b.mnc;
    rs.mns = min(a.mn, b.mns);
  }
  return rs;
}
struct segment_tree_beats {
  node st[4 * MX];
  bool break_condition(int nd, int val, int tp) {
    if (tp == 1) return false;
    if (tp == 2) return st[nd].mn >= val;
    if (tp == 3) return st[nd].mx <= val;
    assert(0);
  }
  bool tag_condition(int nd, int val, int tp) {
    if (tp == 1) return true;
    if (tp == 2) return st[nd].mns > val;
    if (tp == 3) return st[nd].mxs < val;
    assert(0);
  }
  void tag(int nd, int cl, int cr, int v, int tp) {
    if (tp == 1) {
      st[nd].sum += (cr - cl + 1) * 1ll * v;
      st[nd].lz += v;
      st[nd].mn += v;
      st[nd].mns += v;
      st[nd].mx += v;
      st[nd].mxs += v;
    } else if (tp == 2) {
      st[nd].sum += (v - st[nd].mn) * 1ll * st[nd].mnc;
      if (st[nd].mx == st[nd].mn) st[nd].mx = v;
      if (st[nd].mxs == st[nd].mn) st[nd].mxs = v;
      st[nd].mn = v;
    } else if (tp == 3) {
      st[nd].sum += (v - st[nd].mx) * 1ll * st[nd].mxc;
      if (st[nd].mn == st[nd].mx) st[nd].mn = v;
      if (st[nd].mns == st[nd].mx) st[nd].mns = v;
      st[nd].mx = v;
    }
  }
  void prop(int nd, int cl, int cr) {
    if (cl != cr) {
      tag(nd * 2, cl, (cl + cr) / 2, st[nd].lz, 1);
      tag(nd * 2 + 1, (cl + cr) / 2 + 1, cr, st[nd].lz, 1);
      st[nd].lz = 0;
      if (!break_condition(nd * 2, st[nd].mn, 2))
        tag(nd * 2, cl, (cl + cr) / 2, st[nd].mn, 2);
      if (!break_condition(nd * 2 + 1, st[nd].mn, 2))
        tag(nd * 2 + 1, (cl + cr) / 2 + 1, cr, st[nd].mn, 2);
      if (!break_condition(nd * 2, st[nd].mx, 3))
        tag(nd * 2, cl, (cl + cr) / 2, st[nd].mx, 3);
      if (!break_condition(nd * 2 + 1, st[nd].mx, 3))
        tag(nd * 2 + 1, (cl + cr) / 2 + 1, cr, st[nd].mx, 3);
    }
  }
  void build(int nd, int cl, int cr, int arr) {
    if (cl == cr) return void(st[nd] = node(arr));
    build(nd * 2, cl, (cl + cr) / 2, arr);
    build(nd * 2 + 1, (cl + cr) / 2 + 1, cr, arr);
    st[nd] = merge(st[nd * 2], st[nd * 2 + 1]);
  }
  void upd(int nd, int cl, int cr, int lf, int rg, int v, int tp) {
    if (rg < cl || cr < lf || break_condition(nd, v, tp)) return;
    if (lf <= cl && cr <= rg && tag_condition(nd, v, tp))
      return void(tag(nd, cl, cr, v, tp));
    prop(nd, cl, cr);
    upd(nd * 2, cl, (cl + cr) / 2, lf, rg, v, tp);
    upd(nd * 2 + 1, (cl + cr) / 2 + 1, cr, lf, rg, v, tp);
    st[nd] = merge(st[nd * 2], st[nd * 2 + 1]);
  }
  long long que(int nd, int cl, int cr, int lf, int rg) {
    if (rg < cl || cr < lf) return 0;
    if (lf <= cl && cr <= rg) return st[nd].sum;
    prop(nd, cl, cr);
    return que(nd * 2, cl, (cl + cr) / 2, lf, rg) +
           que(nd * 2 + 1, (cl + cr) / 2 + 1, cr, lf, rg);
  }
  void print(int nd, int cl, int cr) {
    cout << nd << " " << st[nd].sum << "\n";
    if (cl == cr) return;
    print(nd * 2, cl, (cl + cr) / 2);
    print(nd * 2 + 1, (cl + cr) / 2 + 1, cr);
  }
} sl, sr;
int fwt[MX];
void updf(int nw, int v) {
  for (; nw < MX; nw += nw & -nw) fwt[nw] += v;
}
int quef(int nw) {
  int rs = 0;
  for (; nw > 0; nw -= nw & -nw) rs += fwt[nw];
  return rs;
}
int n, a[MX];
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  sl.build(1, 1, n, MX);
  sr.build(1, 1, n, -MX);
  for (int x, i = 1; i <= n; i++) {
    cin >> x;
    a[x] = i;
  }
  for (int ps, i = 1; i <= n; i++) {
    ps = a[i];
    sl.upd(1, 1, n, ps, ps, 1, 3);
    sr.upd(1, 1, n, ps, ps, i, 2);
    sl.upd(1, 1, n, ps + 1, n, 1, 1);
    sr.upd(1, 1, n, ps + 1, n, 1, 1);
    int pf = quef(ps);
    sl.upd(1, 1, n, ps + 1, n, pf + 2, 2);
    sr.upd(1, 1, n, 1, ps - 1, pf, 3);
    cout << sr.que(1, 1, n, 1, n) - sl.que(1, 1, n, 1, n) + 2ll * MX * (n - i) +
                i
         << "\n";
    updf(ps, 1);
  }
  return 0;
}
