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 = 150005;
using ll = long long;
int n, a[N], b[N], c[N];
inline int lowbit(int x) { return x & -x; }
void add(int x) {
  while (x <= n) ++c[x], x += lowbit(x);
}
int query(int x) {
  int ret = 0;
  while (x) ret += c[x], x -= lowbit(x);
  return ret;
}
struct TNode {
  struct Node {
    int val, cnt;
    inline bool operator<(const Node &rhs) const { return val < rhs.val; }
    Node operator+(const Node &rhs) const {
      return val == rhs.val ? Node{val, cnt + rhs.cnt} : max(*this, rhs);
    }
  } x, y;
  ll sum;
  int tgmx, tgs, sz, l, r;
  inline int val() { return x.val; }
  inline void addmx(ll v) { sum += v * x.cnt, x.val += v, tgmx += v; }
  inline void addsum(ll v) {
    sum += v * sz;
    tgs += v;
    if (x.cnt) x.val += v;
    if (y.cnt) y.val += v;
  }
  TNode() : x({0, 0}), y({INT_MIN >> 2, 0}), sum(0), tgmx(0), tgs(0), sz(0) {}
} t[N << 2];
inline int lc(int pos) { return pos << 1; }
inline int rc(int pos) { return pos << 1 | 1; }
inline void pushup(int pos) {
  t[pos].sum = t[lc(pos)].sum + t[rc(pos)].sum;
  t[pos].x = t[lc(pos)].x + t[rc(pos)].x;
  if (t[lc(pos)].val() == t[rc(pos)].val())
    t[pos].y = t[lc(pos)].y + t[rc(pos)].y;
  else
    t[pos].y = t[lc(pos)].y + t[rc(pos)].y + min(t[lc(pos)].x, t[rc(pos)].x);
}
inline void pushdown(int pos) {
  int tmp = max(t[lc(pos)].val(), t[rc(pos)].val());
  if (t[lc(pos)].val() == tmp) t[lc(pos)].addmx(t[pos].tgmx);
  if (t[rc(pos)].val() == tmp) t[rc(pos)].addmx(t[pos].tgmx);
  t[lc(pos)].addsum(t[pos].tgs);
  t[rc(pos)].addsum(t[pos].tgs);
  t[pos].tgmx = t[pos].tgs = 0;
}
void build(int pos, int l, int r) {
  t[pos] = TNode();
  t[pos].l = l;
  t[pos].r = r;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(lc(pos), l, mid);
  build(rc(pos), mid + 1, r);
}
void dfs(int pos, int v) {
  if (t[pos].val() <= v) return;
  if (t[pos].y.val < v) return t[pos].addmx(v - t[pos].val());
  pushdown(pos);
  dfs(lc(pos), v);
  dfs(rc(pos), v);
  pushup(pos);
}
void modify(int pos, int l, int r, int v) {
  if (t[pos].l == l && t[pos].r == r) return dfs(pos, v);
  int mid = (t[pos].l + t[pos].r) >> 1;
  pushdown(pos);
  if (r <= mid)
    modify(lc(pos), l, r, v);
  else if (l > mid)
    modify(rc(pos), l, r, v);
  else
    modify(lc(pos), l, mid, v), modify(rc(pos), mid + 1, r, v);
  pushup(pos);
}
void ins(int pos, int l, int r, int v, int fl) {
  t[pos].sz += fl;
  if (t[pos].l == l && t[pos].r == r) {
    if (fl) t[pos].x.cnt = 1;
    return t[pos].addsum(v);
  }
  int mid = (t[pos].l + t[pos].r) >> 1;
  pushdown(pos);
  if (r <= mid)
    ins(lc(pos), l, r, v, fl);
  else if (l > mid)
    ins(rc(pos), l, r, v, fl);
  else
    ins(lc(pos), l, mid, v, fl), ins(rc(pos), mid + 1, r, v, fl);
  pushup(pos);
}
ll ans[N];
void solve() {
  build(1, 1, n);
  memset(c, 0, sizeof(int) * (n + 1));
  for (int i = 1; i <= n; i++) b[a[i]] = i;
  for (int i = 1; i <= n; i++) {
    modify(1, 1, b[i], query(b[i]));
    ins(1, b[i], b[i], i - 1, 1);
    ins(1, b[i], n, 1, 0);
    add(b[i]);
    ans[i] += t[1].sum;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  solve();
  reverse(a + 1, a + n + 1);
  solve();
  for (int i = 1; i <= n; i++) cout << ans[i] - ll(i) * i << endl;
  return 0;
}
