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 MAX_N = 5 + 2e5;
struct BIT {
  int c[MAX_N], top;
  inline void init(int n) {
    memset(c, 0, sizeof(int) * (n + 1));
    top = n;
  }
  inline void add(int x, int key) {
    for (; x <= top; x += x & -x) c[x] += key;
  }
  inline int query(int x) {
    int ret = 0;
    for (; x; x -= x & -x) ret += c[x];
    return ret;
  }
} bit1, bit2;
struct SEG {
  struct Key {
    int mx1, mx2, cnt;
  };
  Key merge(Key a, Key b) {
    if (a.mx1 < b.mx1) swap(a, b);
    if (a.mx1 == b.mx1)
      return (Key){a.mx1, max(a.mx2, b.mx2), a.cnt + b.cnt};
    else
      return (Key){a.mx1, max(a.mx2, b.mx1), a.cnt};
  }
  struct Node {
    Key a;
    int tag;
  } t[MAX_N << 2];
  long long ans;
  void up(int x) { t[x].a = merge(t[x + x].a, t[x + x + 1].a); }
  void build(int p, int l, int r) {
    t[p].a = (Key){0, 0, 0};
    t[p].tag = 1e9;
    if (l == r) return;
    int m = l + r >> 1;
    build(p + p, l, m);
    build(p + p + 1, m + 1, r);
  }
  void init(int l, int r) {
    ans = 0;
    bit1.init(r);
    bit2.init(r);
    bit1.add(r, 1);
    build(1, l, r);
  }
  inline void add2(int key, int cnt) {
    ans += 1ll * bit1.query(key) * cnt;
    bit2.add(key, cnt);
  }
  void put_tag(int x, int tag) {
    if (t[x].a.mx1 < tag) return;
    t[x].a.mx1 = tag;
    t[x].tag = tag;
    if (t[x].a.mx2 > tag) assert(0);
  }
  inline void down(int x) {
    put_tag(x + x, t[x].tag);
    put_tag(x + x + 1, t[x].tag);
    t[x].tag = 1e9;
  }
  void change(int p, int l, int r, int x, int y, int tag) {
    if (l == x && r == y) {
      if (t[p].a.mx1 < tag) return;
      if (t[p].a.mx2 < tag) {
        add2(tag, t[p].a.cnt);
        add2(t[p].a.mx1, -t[p].a.cnt);
        t[p].a.mx1 = tag;
        t[p].tag = tag;
        return;
      }
    }
    if (l == r) return;
    int m = l + r >> 1;
    down(p);
    if (y <= m)
      change(p + p, l, m, x, y, tag);
    else if (x > m)
      change(p + p + 1, m + 1, r, x, y, tag);
    else
      change(p + p, l, m, x, m, tag),
          change(p + p + 1, m + 1, r, m + 1, y, tag);
    up(p);
  }
  void insert(int p, int l, int r, int x, int key) {
    if (l == r) {
      t[p].a = (Key){key, 0, 1};
      add2(key, 1);
      bit1.add(x, 1);
      ans += bit2.query(bit2.top) - bit2.query(x - 1);
      return;
    }
    int m = l + r >> 1;
    down(p);
    if (x <= m)
      insert(p + p, l, m, x, key);
    else
      insert(p + p + 1, m + 1, r, x, key);
    up(p);
  }
  inline long long query() { return ans; }
} seg;
void solve(int a[], long long ans[], int n) {
  seg.init(0, n + 1);
  static int pos[MAX_N];
  for (int i = 1; i <= n; ++i) pos[a[i]] = i;
  for (int i = 1; i <= n; ++i) {
    seg.change(1, 0, n + 1, 0, pos[i], pos[i]);
    seg.insert(1, 0, n + 1, pos[i], n + 1);
    ans[i] = seg.query();
  }
}
int a[MAX_N];
long long ans1[MAX_N], ans2[MAX_N];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  solve(a, ans1, n);
  reverse(a + 1, a + n + 1);
  solve(a, ans2, n);
  for (int i = 1; i <= n; ++i)
    printf("%lld\n", ans1[i] + ans2[i] - 1ll * (i + 2) * i);
  return 0;
}
