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 MOD = 998244353;
struct jlst {
  int adv[524288], eqv[524288];
  int max0[524288], max1[524288], mcnt[524288];
  long long sum[524288];
  void do_add(int cv, int x, int cl) {
    sum[cv] += 1LL * cl * x;
    adv[cv] += x;
    eqv[cv] += x;
    max0[cv] += x;
    if (max1[cv] != -1) max1[cv] += x;
  }
  void do_lmin(int cv, int x) {
    if (max0[cv] <= x) return;
    sum[cv] -= 1LL * mcnt[cv] * (max0[cv] - x);
    max0[cv] = x;
    eqv[cv] = x;
  }
  void pushdown(int cv, int cl) {
    do_add(cv << 1, adv[cv], cl);
    do_add(cv << 1 | 1, adv[cv], cl);
    do_lmin(cv << 1, eqv[cv]);
    do_lmin(cv << 1 | 1, eqv[cv]);
    adv[cv] = 0;
  }
  void pushup(int cv) {
    sum[cv] = sum[cv << 1] + sum[cv << 1 | 1];
    if (max0[cv << 1] == max0[cv << 1 | 1]) {
      max0[cv] = max0[cv << 1];
      mcnt[cv] = mcnt[cv << 1] + mcnt[cv << 1 | 1];
      max1[cv] = max(max1[cv << 1], max1[cv << 1 | 1]);
    } else if (max0[cv << 1] > max0[cv << 1 | 1]) {
      max0[cv] = max0[cv << 1];
      mcnt[cv] = mcnt[cv << 1];
      max1[cv] = max(max1[cv << 1], max0[cv << 1 | 1]);
    } else {
      max0[cv] = max0[cv << 1 | 1];
      mcnt[cv] = mcnt[cv << 1 | 1];
      max1[cv] = max(max0[cv << 1], max1[cv << 1 | 1]);
    }
    adv[cv] = 0;
    eqv[cv] = max0[cv];
  }
  void init() {
    memset(adv, 0, sizeof(adv));
    memset(eqv, 0, sizeof(eqv));
    memset(max0, 0, sizeof(max0));
    memset(max1, -1, sizeof(max1));
    for (int i = 524287; i >= 0; i--)
      mcnt[i] = i >= 262144 ? 1 : (mcnt[i << 1] << 1);
    memset(sum, 0, sizeof(sum));
  }
  void modify(int id, int x, int cv = 1, int cl = 0, int cr = 262143) {
    if (cl == cr) {
      adv[cv] = 0;
      eqv[cv] = x;
      max0[cv] = x;
      max1[cv] = -1;
      mcnt[cv] = 1;
      sum[cv] = x;
      return;
    }
    pushdown(cv, (cr - cl + 1) / 2);
    int mid = cl + cr >> 1;
    if (id <= mid)
      modify(id, x, cv << 1, cl, mid);
    else
      modify(id, x, cv << 1 | 1, mid + 1, cr);
    pushup(cv);
  }
  void add(int l, int r, int x, int cv = 1, int cl = 0, int cr = 262143) {
    if (l > r) return;
    if (l == cl && r == cr) {
      do_add(cv, x, cr - cl + 1);
      return;
    }
    pushdown(cv, (cr - cl + 1) / 2);
    int mid = cl + cr >> 1;
    if (l <= mid) add(l, min(r, mid), x, cv << 1, cl, mid);
    if (r > mid) add(max(l, mid + 1), r, x, cv << 1 | 1, mid + 1, cr);
    pushup(cv);
  }
  void getmin(int l, int r, int x, int cv = 1, int cl = 0, int cr = 262143) {
    if (l > r) return;
    if (l == cl && r == cr && max1[cv] < x) {
      do_lmin(cv, x);
      return;
    }
    pushdown(cv, (cr - cl + 1) / 2);
    int mid = cl + cr >> 1;
    if (l <= mid) getmin(l, min(r, mid), x, cv << 1, cl, mid);
    if (r > mid) getmin(max(l, mid + 1), r, x, cv << 1 | 1, mid + 1, cr);
    pushup(cv);
  }
  long long query(int l, int r, int cv = 1, int cl = 0, int cr = 262143) {
    if (l > r) return 0;
    if (l == cl && r == cr) return sum[cv];
    pushdown(cv, (cr - cl + 1) / 2);
    int mid = cl + cr >> 1;
    long long ret = 0;
    if (l <= mid) ret += query(l, min(r, mid), cv << 1, cl, mid);
    if (r > mid) ret += query(max(l, mid + 1), r, cv << 1 | 1, mid + 1, cr);
    return ret;
  }
} tl, tr;
int n, a[150005], pos[150005];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= (int)(n); i++) scanf("%d", &a[i]);
  for (int i = 1; i <= (int)(n); i++) pos[a[i]] = i;
  for (int i = 1; i <= (int)(n); i++) {
    tl.modify(i, n);
    tr.modify(i, 0);
  }
  for (int i = 1; i <= (int)(n); i++) {
    tl.add(pos[i] + 1, n, -1);
    tr.add(pos[i] + 1, n, 1);
    int cur = tr.query(pos[i], pos[i]);
    tl.modify(pos[i], n);
    tr.modify(pos[i], i);
    tr.getmin(1, pos[i] - 1, cur);
    tl.getmin(pos[i] + 1, n, n - cur - 1);
    printf("%lld\n", tr.query(1, n) + tl.query(1, n) - 1LL * n * n);
  }
  return 0;
}
