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;
int a[150000], pos[150000];
int l[150000], r[150000];
vector<pair<int, int> > tree[1 << 19];
int update(int s, int e, int as, int ae, int i, pair<int, int> p) {
  if ((s > ae) || (e < as))
    return 0;
  else if ((s >= as) && (e <= ae)) {
    tree[i].push_back(p);
    return 0;
  }
  int mid = (s + e) / 2;
  update(s, mid, as, ae, 2 * i + 1, p),
      update(mid + 1, e, as, ae, 2 * i + 2, p);
  return 0;
}
vector<pair<int, int> > cand;
int query(int s, int e, int q, int i) {
  if ((s > q) || (e < q))
    return 0;
  else if (s == e) {
    while (!tree[i].empty()) cand.push_back(tree[i].back()), tree[i].pop_back();
    return 0;
  }
  int mid = (s + e) / 2;
  query(s, mid, q, 2 * i + 1), query(mid + 1, e, q, 2 * i + 2);
  while (!tree[i].empty()) cand.push_back(tree[i].back()), tree[i].pop_back();
  return 0;
}
long long int ans = 1;
struct node {
  node *l, *r, *p;
  int k, s, size, vir;
};
node *nodes[150000];
int size(node *r) {
  if (r == NULL)
    return 0;
  else
    return r->s;
}
int ssize(node *r) {
  if (r == NULL)
    return 0;
  else
    return r->size;
}
int update(node *r) {
  if (r != NULL) {
    r->s = size(r->l) + size(r->r) + 1;
    r->size = ssize(r->l) + ssize(r->r) + r->vir + 1;
  }
  return 0;
}
int isRoot(node *r) {
  return (r->p == NULL) || ((r->p->l != r) && (r->p->r != r));
}
int rotL(node *r) {
  node *n = r->r;
  r->r = n->l;
  if (n->l != NULL) n->l->p = r;
  n->p = r->p;
  if (r->p != NULL) {
    if (r->p->l == r)
      r->p->l = n;
    else if (r->p->r == r)
      r->p->r = n;
  }
  n->l = r, r->p = n;
  update(r), update(n);
  return 0;
}
int rotR(node *r) {
  node *n = r->l;
  r->l = n->r;
  if (n->r != NULL) n->r->p = r;
  n->p = r->p;
  if (r->p != NULL) {
    if (r->p->l == r)
      r->p->l = n;
    else if (r->p->r == r)
      r->p->r = n;
  }
  n->r = r, r->p = n;
  update(r), update(n);
  return 0;
}
int splay(node *n) {
  if (n == NULL) return 0;
  while (!isRoot(n)) {
    if (isRoot(n->p)) {
      if (n == n->p->l)
        rotR(n->p);
      else
        rotL(n->p);
    } else if ((n->p->l == n) && (n->p->p->l == n->p))
      rotR(n->p->p), rotR(n->p);
    else if ((n->p->r == n) && (n->p->p->r == n->p))
      rotL(n->p->p), rotL(n->p);
    else if ((n->p->l == n) && (n->p->p->r == n->p))
      rotR(n->p), rotL(n->p);
    else
      rotL(n->p), rotR(n->p);
  }
  return 0;
}
int access(node *n) {
  node *p = NULL, *o = n;
  while (n != NULL) {
    splay(n);
    n->vir -= ssize(p), n->vir += ssize(n->r);
    n->r = p, update(n), p = n, n = n->p;
  }
  splay(o);
  return 0;
}
int find(int k) {
  node *n = nodes[k];
  access(n);
  while (n->l != NULL) n = n->l;
  splay(n);
  return n->k;
}
int depth(int k) {
  access(nodes[k]);
  return nodes[k]->s - 1;
}
int getSize(int a) {
  if (a == -1)
    return 0;
  else
    return getSize(l[a]) + getSize(r[a]) + 1;
}
int link(int a, int b) {
  access(nodes[a]);
  ans += (long long int)(depth(b) + 1) * nodes[a]->size;
  nodes[a]->p = nodes[b], nodes[b]->vir += nodes[a]->size;
  access(nodes[a]);
  return 0;
}
int cut(int k) {
  node *n = nodes[k];
  access(n);
  int d = n->s - 1;
  n->l->p = NULL;
  n->l = NULL;
  update(n);
  ans -= (long long int)d * n->size;
  return 0;
}
int main() {
  int i;
  int n;
  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%d", &a[i]), pos[--a[i]] = i;
  int j;
  for (i = 0; i < n; i++) {
    l[i] = r[i] = -1;
    nodes[i] = new node;
    nodes[i]->l = nodes[i]->r = nodes[i]->p = NULL;
    nodes[i]->k = i, nodes[i]->s = 1, nodes[i]->size = 1, nodes[i]->vir = 0;
  }
  printf("1\n");
  int sum = 0;
  for (i = 1; i < n; i++) {
    cand.clear(), query(0, n - 1, pos[i], 0);
    vector<int> L, R;
    for (j = 0; j < cand.size(); j++) {
      if (cand[j].second > cand[j].first) {
        if (r[cand[j].first] == cand[j].second) {
          cut(cand[j].second), r[cand[j].first] = -1;
          L.push_back(cand[j].first), R.push_back(cand[j].second);
        }
      } else {
        if (l[cand[j].first] == cand[j].second) {
          cut(cand[j].second), l[cand[j].first] = -1;
          R.push_back(cand[j].first), L.push_back(cand[j].second);
        }
      }
    }
    sum += L.size() + R.size();
    sort(L.begin(), L.end()), sort(R.begin(), R.end(), greater<int>());
    for (j = (pos[i - 1] < pos[i]) ? 0 : 1; j + 1 < L.size(); j += 2) {
      r[L[j]] = (L[j] == L[j + 1]) ? -1 : L[j + 1];
      if (r[L[j]] != -1) {
        link(r[L[j]], L[j]);
        update(0, n - 1, L[j], r[L[j]], 0, make_pair(L[j], r[L[j]]));
      }
    }
    for (j = (pos[i - 1] > pos[i]) ? 0 : 1; j + 1 < R.size(); j += 2) {
      l[R[j]] = (R[j] == R[j + 1]) ? -1 : R[j + 1];
      if (l[R[j]] != -1) {
        link(l[R[j]], R[j]);
        update(0, n - 1, l[R[j]], R[j], 0, make_pair(R[j], l[R[j]]));
      }
    }
    int ll = -1, rr = -1;
    if (pos[i - 1] < pos[i])
      ll = pos[i - 1], rr = R.empty() ? -1 : R[0];
    else
      rr = pos[i - 1], ll = L.empty() ? -1 : L[0];
    l[pos[i]] = ll, r[pos[i]] = rr;
    if (ll != -1) {
      link(ll, pos[i]);
      update(0, n - 1, ll, pos[i], 0, make_pair(pos[i], ll));
    }
    if (rr != -1) {
      link(rr, pos[i]);
      update(0, n - 1, pos[i], rr, 0, make_pair(pos[i], rr));
    }
    ans++;
    printf("%I64d\n", ans);
  }
  return 0;
}
