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;
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool f = false;
  for (; !isdigit(c); c = getchar()) f |= c == '-';
  for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
  if (f) x = -x;
}
template <typename T, typename... Arg>
inline void read(T &x, Arg &...args) {
  read(x);
  read(args...);
}
template <typename T>
inline void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}
const int N = 1.5e5 + 10;
const int inf = 2e9;
int n, a[N];
pair<int, int> p[N];
long long ans[N];
long long sum[N << 2];
int mx1[N << 2];
int smx[N << 2];
int mx2[N << 2];
int cnt[N << 2];
int tag[N << 2];
int lazy[N << 2];
void pushup(int x) {
  sum[x] = sum[(x << 1)] + sum[(x << 1 | 1)];
  cnt[x] = cnt[(x << 1)] + cnt[(x << 1 | 1)];
  if (mx1[(x << 1)] == mx1[(x << 1 | 1)]) {
    mx1[x] = mx1[(x << 1)];
    smx[x] = smx[(x << 1)] + smx[(x << 1 | 1)];
    mx2[x] = max(mx2[(x << 1)], mx2[(x << 1 | 1)]);
  } else {
    mx1[x] = max(mx1[(x << 1)], mx1[(x << 1 | 1)]);
    smx[x] =
        mx1[(x << 1)] > mx1[(x << 1 | 1)] ? smx[(x << 1)] : smx[(x << 1 | 1)];
    mx2[x] = max(min(mx1[(x << 1)], mx1[(x << 1 | 1)]),
                 max(mx2[(x << 1)], mx2[(x << 1 | 1)]));
  }
}
void upd(int x, int k1, int k2) {
  sum[x] += 1ll * k1 * smx[x];
  sum[x] += 1ll * k2 * (cnt[x] - smx[x]);
  if (mx1[x] != -inf) mx1[x] += k1;
  tag[x] += k1;
  if (mx2[x] != -inf) mx2[x] += k2;
  lazy[x] += k2;
}
void pushdown(int x) {
  int _ = max(mx1[(x << 1)], mx1[(x << 1 | 1)]);
  if (mx1[(x << 1)] == _)
    upd((x << 1), tag[x], lazy[x]);
  else
    upd((x << 1), lazy[x], lazy[x]);
  if (mx1[(x << 1 | 1)] == _)
    upd((x << 1 | 1), tag[x], lazy[x]);
  else
    upd((x << 1 | 1), lazy[x], lazy[x]);
  lazy[x] = tag[x] = 0;
}
void build(int x, int l, int r) {
  if (l == r) {
    mx1[x] = -inf;
    smx[x] = 0;
    mx2[x] = -inf;
    cnt[x] = 0;
    sum[x] = 0;
    return;
  }
  build((x << 1), l, ((l + r) >> 1));
  build((x << 1 | 1), ((l + r) >> 1) + 1, r);
  pushup(x);
}
void Plus(int x, int l, int r, int ql, int qr, int val) {
  if (r < ql || qr < l) return;
  if (ql <= l && r <= qr) {
    upd(x, val, val);
    return;
  }
  pushdown(x);
  Plus((x << 1), l, ((l + r) >> 1), ql, qr, val);
  Plus((x << 1 | 1), ((l + r) >> 1) + 1, r, ql, qr, val);
  pushup(x);
}
void Min(int x, int l, int r, int ql, int qr, int A) {
  if (r < ql || qr < l || mx1[x] <= A) return;
  if (ql <= l && r <= qr && mx2[x] < A) {
    upd(x, A - mx1[x], 0);
    return;
  }
  pushdown(x);
  Min((x << 1), l, ((l + r) >> 1), ql, qr, A);
  Min((x << 1 | 1), ((l + r) >> 1) + 1, r, ql, qr, A);
  pushup(x);
}
void Ins(int x, int l, int r, int pos, int val) {
  if (l == r) {
    sum[x] = mx1[x] = val;
    smx[x] = cnt[x] = 1;
    cnt[x] = 1;
    return;
  }
  pushdown(x);
  if (pos <= ((l + r) >> 1))
    Ins((x << 1), l, ((l + r) >> 1), pos, val);
  else
    Ins((x << 1 | 1), ((l + r) >> 1) + 1, r, pos, val);
  pushup(x);
}
long long Sum(int x, int l, int r, int ql, int qr) {
  if (r < ql || qr < l) return 0;
  if (ql <= l && r <= qr) return sum[x];
  pushdown(x);
  return Sum((x << 1), l, ((l + r) >> 1), ql, qr) +
         Sum((x << 1 | 1), ((l + r) >> 1) + 1, r, ql, qr);
}
int Cnt(int x, int l, int r, int ql, int qr) {
  if (r < ql || qr < l) return 0;
  if (ql <= l && r <= qr) return cnt[x];
  pushdown(x);
  return Cnt((x << 1), l, ((l + r) >> 1), ql, qr) +
         Cnt((x << 1 | 1), ((l + r) >> 1) + 1, r, ql, qr);
}
signed main() {
  read(n);
  for (int i = 1; i <= n; i++) read(a[i]), p[i] = {a[i], i};
  sort(p + 1, p + 1 + n);
  for (int SS = 1; SS <= 2; SS++) {
    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
      int pos = p[i].second;
      int pre = Cnt(1, 1, n, 1, pos);
      if (pos != 1) Min(1, 1, n, 1, pos - 1, pre + 1);
      if (pos != n) Plus(1, 1, n, pos + 1, n, 1);
      Ins(1, 1, n, pos, i + 1);
      ans[i] += sum[1];
    }
    for (int i = 1; i <= n; i++) p[i].second = n - p[i].second + 1;
  }
  for (int i = 1; i <= n; i++) write(ans[i] - 1ll * i * (i + 2)), putchar('\n');
}
