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;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int arr[300005], pr[300005], loc[300005];
struct Treap {
  int key;
  Treap *l = NULL, *r = NULL;
  int mn1 = 0, mn2 = 300005, cnt1 = 1, a = 0, lz = 0, con = 0, sz = 1;
  long long s = 0;
  Treap(int _key) { key = _key; }
  void refresh() {
    s = mn1 = a;
    cnt1 = 1;
    mn2 = 300005;
    sz = 1;
    if (l) {
      sz += l->sz;
      l->update();
      s += l->s;
      if (l->mn1 < mn1) {
        mn2 = mn1;
        mn1 = l->mn1;
        cnt1 = l->cnt1;
      } else if (l->mn1 == mn1) {
        cnt1 += l->cnt1;
      } else
        mn2 = min(l->mn1, mn2);
      mn2 = min(mn2, l->mn2);
    }
    if (r) {
      r->update();
      sz += r->sz;
      s += r->s;
      if (r->mn1 < mn1) {
        mn2 = mn1;
        mn1 = r->mn1;
        cnt1 = r->cnt1;
      } else if (r->mn1 == mn1) {
        cnt1 += r->cnt1;
      } else
        mn2 = min(r->mn1, mn2);
      mn2 = min(mn2, r->mn2);
    }
  }
  void update() {
    mn1 += con;
    mn2 += con;
    s += 1LL * con * sz;
    a += con;
    if (l) {
      l->con += con;
      l->lz += con;
    }
    if (r) {
      r->con += con;
      r->lz += con;
    }
    con = 0;
    if (mn1 >= lz) {
      lz = 0;
      return;
    }
    if (l) l->lz = max(l->lz, lz);
    if (r) r->lz = max(r->lz, lz);
    a = max(a, lz);
    if (mn2 > lz) {
      s += 1LL * (lz - mn1) * cnt1;
      mn1 = lz;
      lz = 0;
      return;
    }
    lz = 0;
    refresh();
  }
}* le = NULL, *ri = NULL;
pair<Treap*, Treap*> sp;
void split(Treap* t, int key) {
  if (!t) {
    sp = {NULL, NULL};
    return;
  }
  t->update();
  if (t->key < key) {
    split(t->r, key);
    t->r = sp.first;
    sp.first = t;
    t->refresh();
  } else {
    split(t->l, key);
    t->l = sp.second;
    sp.second = t;
    t->refresh();
  }
}
Treap* merge(Treap* l, Treap* r) {
  if (l) l->update();
  if (r) r->update();
  if (!l || !r) return l ? l : r;
  if (pr[l->key] < pr[r->key]) {
    r->l = merge(l, r->l);
    r->refresh();
    return r;
  }
  l->r = merge(l->r, r);
  l->refresh();
  return l;
}
void update(Treap*& t, int key, int lz) {
  split(t, key);
  if (sp.second) {
    ++sp.second->con;
    sp.second->lz = max(lz, sp.second->lz);
  }
  t = merge(sp.first, sp.second);
}
Treap* insert(Treap* t, int key) {
  if (!t) {
    t = new Treap(key);
  } else if (pr[t->key] > pr[key]) {
    t->update();
    if (t->key < key)
      t->r = insert(t->r, key);
    else
      t->l = insert(t->l, key);
  } else {
    t->update();
    split(t, key);
    t = new Treap(key);
    t->l = sp.first;
    t->r = sp.second;
  }
  t->refresh();
  return t;
}
int n;
int bit[300005];
void updatebit(int x) {
  while (x <= n) {
    ++bit[x];
    x += x & -x;
  }
}
int get(int x) {
  int s = 0;
  while (x) {
    s += bit[x];
    x -= x & -x;
  }
  return s;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> arr[i];
    loc[arr[i]] = i;
    pr[i] = i;
  }
  shuffle(pr + 1, pr + n + 1, rng);
  for (int i = 1; i <= n; ++i) {
    updatebit(loc[i]);
    int k = get(loc[i]);
    update(le, loc[i], k);
    le = insert(le, loc[i]);
    update(ri, n + 1 - loc[i], i + 1 - k);
    ri = insert(ri, n + 1 - loc[i]);
    cout << 1LL * i * i - le->s - ri->s << '\n';
  }
}
