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;
inline long long read() {
  char ch = getchar();
  long long nega = 1;
  while (!isdigit(ch)) {
    if (ch == '-') nega = -1;
    ch = getchar();
  }
  long long ans = 0;
  while (isdigit(ch)) {
    ans = ans * 10 + ch - 48;
    ch = getchar();
  }
  if (nega == -1) return -ans;
  return ans;
}
long long a[150005], rev[150005], n;
struct SMT1 {
  long long a[150005 * 4], tag[150005 * 4], b[150005 * 4], ans[150005 * 4];
  inline void doit(long long u, long long v) {
    a[u] += v, tag[u] += v, ans[u] += v * b[u];
  }
  inline void pushdown(long long u) {
    doit((u << 1), tag[u]), doit((u << 1 | 1), tag[u]);
    tag[u] = 0;
  }
  void upd1(long long u, long long l, long long r, long long pl, long long v) {
    if (pl < 1 || pl > n) return;
    if (l == r) {
      b[u] += v, ans[u] = a[u] * b[u];
      return;
    }
    pushdown(u);
    if (pl <= ((l + r) / 2))
      upd1((u << 1), l, ((l + r) / 2), pl, v);
    else
      upd1((u << 1 | 1), ((l + r) / 2) + 1, r, pl, v);
    ans[u] = ans[(u << 1)] + ans[(u << 1 | 1)],
    b[u] = b[(u << 1)] + b[(u << 1 | 1)], a[u] = a[(u << 1)] + a[(u << 1 | 1)];
  }
  void upd2(long long u, long long l, long long r, long long L, long long R,
            long long v) {
    if (L <= l && r <= R) {
      a[u] += v, tag[u] += v;
      ans[u] += v * b[u];
      return;
    }
    pushdown(u);
    if (((l + r) / 2) >= L) upd2((u << 1), l, ((l + r) / 2), L, R, v);
    if (((l + r) / 2) < R) upd2((u << 1 | 1), ((l + r) / 2) + 1, r, L, R, v);
    ans[u] = ans[(u << 1)] + ans[(u << 1 | 1)],
    b[u] = b[(u << 1)] + b[(u << 1 | 1)], a[u] = a[(u << 1)] + a[(u << 1 | 1)];
  }
  long long query() { return ans[1]; }
} smt1;
struct SMT2 {
  struct Node {
    long long mx1, mx2, ct, tag;
  };
  Node t[150005 * 4];
  inline Node merge(Node u, Node v) {
    Node ans;
    if (u.mx1 == v.mx1) {
      ans.mx1 = u.mx1, ans.mx2 = max(u.mx2, v.mx2);
      ans.ct = u.ct + v.ct;
    } else if (u.mx1 > v.mx1) {
      ans.mx1 = u.mx1, ans.mx2 = max(u.mx2, v.mx1);
      ans.ct = u.ct;
    } else {
      ans.mx1 = v.mx1, ans.mx2 = max(u.mx1, v.mx2);
      ans.ct = v.ct;
    }
    return ans;
  }
  void update(long long u, long long l, long long r, long long L, long long R,
              long long v, long long qaq);
  void build(long long u, long long l, long long r) {
    if (l == r) {
      t[u].mx1 = 0;
      return;
    }
    build((u << 1), l, ((l + r) / 2)),
        build((u << 1 | 1), ((l + r) / 2) + 1, r);
    t[u] = merge(t[(u << 1)], t[(u << 1 | 1)]);
  }
  void pushdown(long long u, long long l, long long r) {
    if (t[u].tag) {
      doit((u << 1), l, ((l + r) / 2), l, ((l + r) / 2), t[u].tag, 0);
      doit((u << 1 | 1), ((l + r) / 2) + 1, r, ((l + r) / 2) + 1, r, t[u].tag,
           0);
      t[u].tag = 0;
    }
  }
  void doit(long long u, long long l, long long r, long long L, long long R,
            long long v, long long qaq) {
    if (t[u].mx1 <= v) return;
    if (l == r) {
      if (qaq)
        if (t[u].mx1 != 150005 && t[u].mx1 != 1)
          smt1.upd1(1, 1, n, t[u].mx1 - 1, -t[u].ct);
      t[u].mx1 = v;
      if (qaq)
        if (t[u].mx1 != 150005 && t[u].mx1 != 1)
          smt1.upd1(1, 1, n, t[u].mx1 - 1, t[u].ct);
      return;
    }
    if (t[u].mx2 < v) {
      if (qaq)
        if (t[u].mx1 != 150005 && t[u].mx1 != 1)
          smt1.upd1(1, 1, n, t[u].mx1 - 1, -t[u].ct);
      t[u].mx1 = v, t[u].tag = v;
      if (qaq)
        if (t[u].mx1 != 150005 && t[u].mx1 != 1)
          smt1.upd1(1, 1, n, t[u].mx1 - 1, t[u].ct);
      return;
    }
    pushdown(u, l, r);
    update((u << 1), l, ((l + r) / 2), L, R, v, qaq),
        update((u << 1 | 1), ((l + r) / 2) + 1, r, L, R, v, qaq);
    t[u] = merge(t[(u << 1)], t[(u << 1 | 1)]);
  }
  void update(long long u, long long l, long long r, long long pl) {
    if (l == r) {
      t[u].mx1 = n + 1, t[u].ct = 1;
      smt1.upd1(1, 1, n, n, t[u].ct);
      return;
    }
    pushdown(u, l, r);
    if (pl <= ((l + r) / 2))
      update((u << 1), l, ((l + r) / 2), pl);
    else
      update((u << 1 | 1), ((l + r) / 2) + 1, r, pl);
    t[u] = merge(t[(u << 1)], t[(u << 1 | 1)]);
  }
} smt2;
void SMT2::update(long long u, long long l, long long r, long long L,
                  long long R, long long v, long long qaq) {
  if (L <= l && r <= R) {
    SMT2::doit(u, l, r, L, R, v, qaq);
    return;
  }
  SMT2::pushdown(u, l, r);
  if (((l + r) / 2) >= L)
    SMT2::update((u << 1), l, ((l + r) / 2), L, R, v, qaq);
  if (((l + r) / 2) < R)
    SMT2::update((u << 1 | 1), ((l + r) / 2) + 1, r, L, R, v, qaq);
  SMT2::t[u] = merge(SMT2::t[(u << 1)], SMT2::t[(u << 1 | 1)]);
}
struct SMT3 {
  struct Node {
    long long mn1, mn2, ct, tag;
  };
  Node t[150005 * 4];
  inline Node merge(Node u, Node v) {
    Node ans;
    if (u.mn1 == v.mn1) {
      ans.mn1 = u.mn1, ans.mn2 = min(u.mn2, v.mn2);
      ans.ct = u.ct + v.ct;
    } else if (u.mn1 < v.mn1) {
      ans.mn1 = u.mn1, ans.mn2 = min(u.mn2, v.mn1);
      ans.ct = u.ct;
    } else {
      ans.mn1 = v.mn1, ans.mn2 = min(u.mn1, v.mn2);
      ans.ct = v.ct;
    }
    return ans;
  }
  void build(long long u, long long l, long long r) {
    if (l == r) {
      t[u].mn1 = 150005;
      return;
    }
    build((u << 1), l, ((l + r) / 2)),
        build((u << 1 | 1), ((l + r) / 2) + 1, r);
    t[u] = merge(t[(u << 1)], t[(u << 1 | 1)]);
  }
  void update(long long u, long long l, long long r, long long L, long long R,
              long long v, long long qaq);
  void pushdown(long long u, long long l, long long r) {
    if (t[u].tag) {
      doit((u << 1), l, ((l + r) / 2), l, ((l + r) / 2), t[u].tag, 0);
      doit((u << 1 | 1), ((l + r) / 2) + 1, r, ((l + r) / 2) + 1, r, t[u].tag,
           0);
      t[u].tag = 0;
    }
  }
  void doit(long long u, long long l, long long r, long long L, long long R,
            long long v, long long qaq) {
    if (t[u].mn1 >= v) return;
    if (l == r) {
      if (qaq)
        if (t[u].mn1 != 0 && t[u].mn1 != 150005)
          smt1.upd1(1, 1, n, t[u].mn1, t[u].ct);
      t[u].mn1 = v;
      if (qaq)
        if (t[u].mn1 != 0 && t[u].mn1 != 150005)
          smt1.upd1(1, 1, n, t[u].mn1, -t[u].ct);
      return;
    }
    if (t[u].mn2 > v) {
      if (qaq)
        if (t[u].mn1 != 0 && t[u].mn1 != 150005)
          smt1.upd1(1, 1, n, t[u].mn1, t[u].ct);
      t[u].mn1 = v, t[u].tag = v;
      if (qaq)
        if (t[u].mn1 != 0 && t[u].mn1 != 150005)
          smt1.upd1(1, 1, n, t[u].mn1, -t[u].ct);
      return;
    }
    pushdown(u, l, r);
    update((u << 1), l, ((l + r) / 2), L, R, v, qaq),
        update((u << 1 | 1), ((l + r) / 2) + 1, r, L, R, v, qaq);
    t[u] = merge(t[(u << 1)], t[(u << 1 | 1)]);
  }
  void update(long long u, long long l, long long r, long long pl) {
    if (l == r) {
      t[u].mn1 = 0, t[u].ct = 1;
      return;
    }
    pushdown(u, l, r);
    if (pl <= ((l + r) / 2))
      update((u << 1), l, ((l + r) / 2), pl);
    else
      update((u << 1 | 1), ((l + r) / 2) + 1, r, pl);
    t[u] = merge(t[(u << 1)], t[(u << 1 | 1)]);
  }
} smt3;
void SMT3::update(long long u, long long l, long long r, long long L,
                  long long R, long long v, long long qaq) {
  if (L <= l && r <= R) {
    SMT3::doit(u, l, r, L, R, v, qaq);
    return;
  }
  SMT3::pushdown(u, l, r);
  if (((l + r) / 2) >= L)
    SMT3::update((u << 1), l, ((l + r) / 2), L, R, v, qaq);
  if (((l + r) / 2) < R)
    SMT3::update((u << 1 | 1), ((l + r) / 2) + 1, r, L, R, v, qaq);
  SMT3::t[u] = merge(SMT3::t[(u << 1)], SMT3::t[(u << 1 | 1)]);
}
signed main() {
  cin >> n;
  for (long long i = 1; i <= n; i++) a[i] = read(), rev[a[i]] = i;
  smt2.build(1, 1, n), smt3.build(1, 1, n);
  for (long long i = 1; i <= n; i++) {
    long long pos = rev[i];
    smt2.update(1, 1, n, 1, pos, pos, 1);
    smt3.update(1, 1, n, pos, n, pos, 1);
    smt3.update(1, 1, n, pos);
    smt2.update(1, 1, n, pos);
    smt1.upd2(1, 1, n, pos, n, 1);
    printf("%lld\n", smt1.query());
  }
  return 0;
}
