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>
const int MAXN = 2e5 + 5;
int ch[MAXN][2], f[MAXN], sz[MAXN], tsz[MAXN], vsz[MAXN], a[MAXN];
long long vans[MAXN], tans[MAXN];
inline bool nroot(int x) { return ch[f[x]][0] == x || ch[f[x]][1] == x; }
inline void pushup(int x) {
  sz[x] = sz[(ch[x][0])] + sz[(ch[x][1])] + 1;
  tsz[x] = tsz[(ch[x][0])] + tsz[(ch[x][1])] + vsz[x] + 1;
  tans[x] = vans[x] + tans[(ch[x][0])] + tans[(ch[x][1])] +
            1ll * (sz[(ch[x][0])] + 1) * (tsz[(ch[x][1])] + vsz[x] + 1);
}
inline void rotate(int x) {
  int y = f[x], z = f[y], k = ch[y][1] == x, w = ch[x][!k];
  if (nroot(y)) ch[z][ch[z][1] == y] = x;
  f[x] = z;
  ch[x][!k] = y;
  f[y] = x;
  ch[y][k] = w;
  if (w) f[w] = y;
  pushup(y);
  pushup(x);
}
inline void splay(int x, int v = 0) {
  while (nroot(x)) {
    int y = f[x], z = f[y];
    if (nroot(y)) rotate((ch[z][1] == y) ^ (ch[y][1] == x) ? x : y);
    rotate(x);
  }
}
inline void access(int x) {
  for (int y = 0; x; x = f[y = x]) {
    splay(x);
    vsz[x] += tsz[(ch[x][1])];
    vans[x] += tans[(ch[x][1])];
    (ch[x][1]) = y;
    vsz[x] -= tsz[y];
    vans[x] -= tans[y];
    pushup(x);
  }
}
inline void cut(int v) {
  access(v);
  splay(v);
  f[ch[v][0]] = 0;
  ch[v][0] = 0;
  pushup(v);
}
inline void link(int u, int v) {
  access(u);
  splay(u);
  f[v] = u;
  ch[u][1] = v;
  pushup(u);
}
inline int findpre(int x, int v) {
  int ans = 0;
  while (x) {
    if (a[x] > v)
      ans = x, x = (ch[x][1]);
    else
      x = (ch[x][0]);
  }
  return ans;
}
inline int findsuf(int x, int v) {
  int ans = 0;
  while (x) {
    if (a[x] < v)
      ans = x, x = (ch[x][0]);
    else
      x = (ch[x][1]);
  }
  return ans;
}
int n, ps[MAXN];
std::set<int> S;
int ls[MAXN], rs[MAXN];
inline void dfs(int x) {
  if (ls[x]) dfs(ls[x]), vans[x] += tans[ls[x]], vsz[x] += tsz[ls[x]];
  if (rs[x]) dfs(rs[x]), vans[x] += tans[rs[x]], vsz[x] += tsz[rs[x]];
  pushup(x);
}
inline void print(int x, std::vector<int> &v) {
  if ((ch[x][0])) print((ch[x][0]), v);
  v.emplace_back(x);
  if ((ch[x][1])) print((ch[x][1]), v);
}
long long res[MAXN];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i)
    scanf("%d", a + i), ps[a[i]] = i, S.insert(i), sz[i] = 1;
  static int st[MAXN], tp = 0;
  for (int i = 1; i <= n; ++i) {
    int k = tp;
    while (tp && a[st[tp]] < a[i]) --tp;
    if (tp) rs[st[tp]] = i, f[i] = st[tp];
    if (tp != k) ls[i] = st[tp + 1], f[st[tp + 1]] = i;
    st[++tp] = i;
  }
  assert(st[1] == ps[n]);
  dfs(ps[n]);
  for (int i = n; i >= 2; --i) {
    int p = ps[i];
    access(p);
    splay(p);
    res[i] = tans[p];
    auto it = S.find(p);
    if (next(it) == S.end() || it == S.begin()) {
      int y = ps[i - 1];
      access(y);
      splay(y);
      cut(y);
    } else {
      int y = *prev(it), z = *next(it);
      access(y);
      splay(y);
      int sy = sz[y];
      access(z);
      splay(z);
      int sz = ::sz[z];
      if (sy < sz) std::swap(y, z), std::swap(sy, sz);
      access(z);
      splay(z);
      std::vector<int> vec;
      print(z, vec);
      for (auto x : vec)
        if (x != p) cut(x);
      std::reverse(vec.begin(), vec.end());
      int now = y;
      for (auto x : vec) {
        if (x == p) continue;
        access(now);
        splay(now);
        int pre = findpre(now, a[x]), suf = findsuf(now, a[x]);
        splay(pre);
        if (suf) splay(suf);
        if (suf) cut(suf);
        if (pre) link(pre, x);
        if (suf) link(x, suf);
        now = x;
      }
      now = y;
      access(now);
      splay(now);
      int t = findsuf(now, i);
      splay(t);
      cut(t);
    }
    S.erase(p);
  }
  res[1] = 1;
  for (int i = 1; i <= n; ++i) printf("%lld\n", res[i]);
  return 0;
}
