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 = 2e5 + 100;
const int inf = 0x3f3f3f3f;
int n, m;
int a[N];
struct segment_tree {
  int mn1[N * 4], mn2[N * 4], mcnt[N * 4];
  int siz[N * 4];
  long long sum[N * 4];
  int mxtag[N * 4], plustag[N * 4];
  inline void push_up(int x) {
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
    siz[x] = siz[x << 1] + siz[x << 1 | 1];
    if (mn1[x << 1] == mn1[x << 1 | 1]) {
      mcnt[x] = mcnt[x << 1] + mcnt[x << 1 | 1];
      mn1[x] = mn1[x << 1];
      mn2[x] = min(mn2[x << 1], mn2[x << 1 | 1]);
    } else if (mn1[x << 1] < mn1[x << 1 | 1]) {
      mn1[x] = mn1[x << 1];
      mcnt[x] = mcnt[x << 1];
      mn2[x] = min(mn2[x << 1], mn1[x << 1 | 1]);
    } else {
      mn1[x] = mn1[x << 1 | 1];
      mcnt[x] = mcnt[x << 1 | 1];
      mn2[x] = min(mn2[x << 1 | 1], mn1[x << 1]);
    }
  }
  inline void build(int x, int l, int r) {
    if (l == r) {
      mn1[x] = mn2[x] = inf;
      siz[x] = sum[x] = mcnt[x] = 0;
      return;
    }
    build(x << 1, l, (l + r) / 2);
    build(x << 1 | 1, (l + r) / 2 + 1, r);
    push_up(x);
  }
  inline void push_down(int x) {
    assert(mxtag[x] < mn2[x]);
    if (siz[x << 1] > 0) {
      sum[x << 1] += 1LL * plustag[x] * siz[x << 1];
      mn1[x << 1] += plustag[x];
      mn2[x << 1] += plustag[x];
      mxtag[x << 1] = max(mxtag[x << 1] + plustag[x], mxtag[x]);
      plustag[x << 1] += plustag[x];
      if (mxtag[x] > mn1[x << 1]) {
        sum[x << 1] += (mxtag[x] - mn1[x << 1]) * mcnt[x << 1];
        mn1[x << 1] = mxtag[x];
      }
    }
    if (siz[x << 1 | 1] > 0) {
      sum[x << 1 | 1] += 1LL * plustag[x] * siz[x << 1 | 1];
      mn1[x << 1 | 1] += plustag[x];
      mn2[x << 1 | 1] += plustag[x];
      mxtag[x << 1 | 1] = max(mxtag[x << 1 | 1] + plustag[x], mxtag[x]);
      plustag[x << 1 | 1] += plustag[x];
      if (mxtag[x] > mn1[x << 1 | 1]) {
        sum[x << 1 | 1] += (mxtag[x] - mn1[x << 1 | 1]) * mcnt[x << 1 | 1];
        mn1[x << 1 | 1] = mxtag[x];
      }
    }
    mxtag[x] = plustag[x] = 0;
  }
  inline void add(int x, int l, int r, int ql, int qr, int v) {
    if (ql > r || qr < l || siz[x] == 0) return;
    if (ql <= l && r <= qr) {
      sum[x] += siz[x] * v;
      mn1[x] += v;
      mn2[x] += v;
      mxtag[x] += v;
      plustag[x] += v;
      return;
    }
    push_down(x);
    add(x << 1, l, (l + r) / 2, ql, qr, v);
    add(x << 1 | 1, (l + r) / 2 + 1, r, ql, qr, v);
    push_up(x);
  }
  inline void chkmax(int x, int l, int r, int ql, int qr, int v) {
    if (ql > r || qr < l || siz[x] == 0) return;
    if (ql <= l && r <= qr) {
      if (v <= mn1[x])
        return;
      else if (v < mn2[x]) {
        sum[x] += 1LL * (v - mn1[x]) * mcnt[x];
        mxtag[x] = max(mxtag[x], v);
        mn1[x] = v;
        return;
      }
    }
    push_down(x);
    chkmax(x << 1, l, (l + r) / 2, ql, qr, v);
    chkmax(x << 1 | 1, (l + r) / 2 + 1, r, ql, qr, v);
    push_up(x);
  }
  inline void insert(int x, int l, int r, int pos, int vx) {
    if (l == r) {
      siz[x] = 1;
      mn1[x] = sum[x] = vx;
      mn2[x] = inf;
      mcnt[x] = 1;
      return;
    }
    push_down(x);
    if (pos <= (l + r) / 2)
      insert(x << 1, l, (l + r) / 2, pos, vx);
    else
      insert(x << 1 | 1, (l + r) / 2 + 1, r, pos, vx);
    push_up(x);
  }
  inline long long query(int x, int l, int r, int ql, int qr) {
    if (ql > r || qr < l || siz[x] == 0) return 0;
    if (ql <= l && r <= qr) {
      return sum[x];
    }
    push_down(x);
    return query(x << 1, l, (l + r) / 2, ql, qr) +
           query(x << 1 | 1, (l + r) / 2 + 1, r, ql, qr);
  }
  inline int qsum(int x, int l, int r, int ql, int qr) {
    if (ql > r || qr < l) return 0;
    if (ql <= l && r <= qr) return siz[x];
    return qsum(x << 1, l, (l + r) / 2, ql, qr) +
           qsum(x << 1 | 1, (l + r) / 2 + 1, r, ql, qr);
  }
} S1, S2;
int pos[N];
int main() {
  scanf("%d", &n);
  S1.build(1, 1, n);
  S2.build(1, 1, n);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i), pos[a[i]] = i;
  for (int i = 1; i <= n; ++i) {
    S1.add(1, 1, n, pos[i] + 1, n, 1);
    S1.chkmax(1, 1, n, pos[i] + 1, n, S1.qsum(1, 1, n, 1, pos[i] - 1) + 2);
    S1.insert(1, 1, n, pos[i], 1);
    S2.add(1, 1, n, n - pos[i] + 2, n, 1);
    S2.chkmax(1, 1, n, n - pos[i] + 2, n, S2.qsum(1, 1, n, 1, n - pos[i]) + 2);
    S2.insert(1, 1, n, n - pos[i] + 1, 1);
    long long ans = (-S1.query(1, 1, n, 1, n) - S2.query(1, 1, n, 1, n)) +
                    1LL * (i + 2) * i;
    printf("%lld\n", ans);
  }
  return 0;
}
