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 long long mod = 1e9 + 7;
long double PI = acosl(-1);
const long long infl = 3e18 + 100;
const int inf = 2e9 + 100;
const int nmax = 15e4 + 5;
const int MAXLG = log2(nmax) + 1;
struct Node {
  int sz = 1, label;
  int asholsz = 1, lazyashol = 0;
  int sodo, boro;
  Node *p, *pp, *l, *r;
  Node() { p = pp = l = r = 0; }
};
void update(Node *x) {
  x->sz = 1;
  x->sodo = x->boro = x->label;
  if (x->l) {
    x->sz += x->l->sz;
    x->sodo = min(x->sodo, x->l->sodo);
    x->boro = max(x->boro, x->l->boro);
  }
  if (x->r) {
    x->sz += x->r->sz;
    x->sodo = min(x->sodo, x->r->sodo);
    x->boro = max(x->boro, x->r->boro);
  }
}
void rotr(Node *x) {
  Node *y, *z;
  y = x->p, z = y->p;
  if ((y->l = x->r)) y->l->p = y;
  x->r = y, y->p = x;
  if ((x->p = z)) {
    if (y == z->l)
      z->l = x;
    else
      z->r = x;
  }
  x->pp = y->pp;
  y->pp = 0;
  update(y);
}
void rotl(Node *x) {
  Node *y, *z;
  y = x->p, z = y->p;
  if ((y->r = x->l)) y->r->p = y;
  x->l = y, y->p = x;
  if ((x->p = z)) {
    if (y == z->l)
      z->l = x;
    else
      z->r = x;
  }
  x->pp = y->pp;
  y->pp = 0;
  update(y);
}
void splay(Node *x) {
  Node *y, *z;
  while (x->p) {
    y = x->p;
    if (y->p == 0) {
      if (x == y->l)
        rotr(x);
      else
        rotl(x);
    } else {
      z = y->p;
      if (y == z->l) {
        if (x == y->l)
          rotr(y), rotr(x);
        else
          rotl(x), rotr(x);
      } else {
        if (x == y->r)
          rotl(y), rotl(x);
        else
          rotr(x), rotl(x);
      }
    }
  }
  update(x);
}
Node *access(Node *x) {
  splay(x);
  if (x->r) {
    x->r->pp = x;
    x->r->p = 0;
    x->r = 0;
    update(x);
  }
  Node *last = x;
  while (x->pp) {
    Node *y = x->pp;
    last = y;
    splay(y);
    if (y->r) {
      y->r->pp = y;
      y->r->p = 0;
    }
    y->r = x;
    x->p = y;
    x->pp = 0;
    update(y);
    splay(x);
  }
  return last;
}
Node *root(Node *x) {
  access(x);
  while (x->l) x = x->l;
  splay(x);
  return x;
}
void cut(Node *x) {
  access(x);
  x->l->p = 0;
  x->l = 0;
  update(x);
}
void link(Node *x, Node *y) {
  access(x);
  access(y);
  x->l = y;
  y->p = x;
  update(x);
}
int depth(Node *x) {
  access(x);
  return x->sz - 1;
}
void puraprintsplaytree(Node *cur) {
  if (!cur) return;
  cout << cur->label << " ";
  puraprintsplaytree(cur->l);
  cout << cur->label << " ";
  puraprintsplaytree(cur->r);
  cout << cur->label << " ";
}
class LinkCut {
 public:
  Node *x;
  LinkCut(int n) {
    x = new Node[n];
    for (int i = 0; i < n; i++) {
      x[i].label = i;
      x[i].sodo = x[i].boro = i;
      update(&x[i]);
    }
  }
  virtual ~LinkCut() { delete[] x; }
  void link(int u, int v) { ::link(&x[u], &x[v]); }
  void cut(int u) { ::cut(&x[u]); }
  void eksess(int u) { ::access(&x[u]); }
  int root(int u) { return ::root(&x[u])->label; }
  void mekrut(int z) {
    Node *u = &x[z];
    access(u);
    splay(u);
    if (u->l) {
      u->l->p = 0;
      u->l->pp = u;
      u->l = 0;
      update(u);
    }
  }
  int depth(int u) { return ::depth(&x[u]); }
  int getsplesize(int u) { return (&x[u])->sz; }
  int bamekhoj(int z) {
    Node *nud = &x[z];
    access(nud);
    if (!(nud->l)) return nud->label;
    Node *cur = nud->l;
    Node *paisi = nud;
    while (true) {
      if (!(cur->r) or cur->r->boro < z) {
        if (cur->label < z) {
          paisi = cur;
          cur = cur->l;
          if (!cur) return paisi->label;
        } else {
          if (!(cur->r)) return paisi->label;
          cur = cur->r;
        }
      } else
        cur = cur->r;
    }
  }
  int danekhoj(int z) {
    Node *nud = &x[z];
    access(nud);
    if (!(nud->l)) return nud->label;
    Node *cur = nud->l;
    Node *paisi = nud;
    while (true) {
      if (!(cur->r) or cur->r->sodo > z) {
        if (cur->label > z) {
          paisi = cur;
          cur = cur->l;
          if (!cur) return paisi->label;
        } else {
          if (!(cur->r)) return paisi->label;
          cur = cur->r;
        }
      } else
        cur = cur->r;
    }
  }
} lct(nmax);
const int N = nmax;
struct Nude {
  int ch[2], fa, vir, siz;
  bool rev;
} t[N];
bool nroot(int x);
void rotate(int x);
void Splay(int x);
void access(int x);
void makeroot(int x);
void split(int x, int y);
void cut(int x, int y);
void link(int x, int y);
void reverse(int x);
void pushup(int x);
void pushdown(int x);
int id, sta[N], top, sx[nmax * 2], sy[nmax * 2], stot;
int koi[nmax];
int arr[nmax];
int sbsz[nmax];
int n;
int par[nmax];
int getsubtreesaiz(int u) {
  int v = par[u];
  assert(v != 0);
  split(u, v);
  return t[u].vir + 1;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    arr[i] = x;
    koi[x] = i;
  }
  long long uttor = 1;
  vector<long long> anss;
  anss.push_back(uttor);
  set<int> nisi;
  nisi.insert(koi[1]);
  for (int i = 2; i <= n; i++) {
    lct.mekrut(koi[i - 1]);
    int idx = koi[i];
    int sodo = idx;
    nisi.insert(idx);
    auto it = nisi.find(idx);
    if (it != nisi.begin()) sodo = *prev(it);
    if (next(it) != nisi.end())
      if (arr[sodo] > arr[*next(it)]) sodo = *next(it);
    vector<int> edit;
    link(koi[i], koi[i - 1]);
    par[koi[i - 1]] = koi[i];
    while (1) {
      int uchunod;
      if (idx < sodo)
        uchunod = lct.danekhoj(sodo);
      else
        uchunod = lct.bamekhoj(sodo);
      edit.push_back(uchunod);
      sbsz[uchunod] = getsubtreesaiz(uchunod);
      uttor -= 1LL * sbsz[uchunod] * (lct.depth(uchunod));
      if (lct.getsplesize(uchunod) == 1) break;
      edit.push_back(par[uchunod]);
      lct.cut(uchunod);
      cut(uchunod, par[uchunod]);
      sodo = par[uchunod];
    }
    vector<pair<int, int> > lagao;
    for (int k = 0; k < edit.size(); k += 2) {
      if (k + 3 < edit.size())
        lagao.push_back({edit[k], edit[k + 3]});
      else
        lagao.push_back({edit[k], koi[i]});
    }
    reverse(lagao.begin(), lagao.end());
    lct.mekrut(koi[i]);
    makeroot(koi[i]);
    for (pair<int, int> z : lagao) {
      int u = z.first, v = z.second;
      lct.link(u, v);
      if (u != koi[i - 1]) link(u, v);
      par[u] = v;
      uttor += 1LL * sbsz[u] * (lct.depth(u));
    }
    uttor++;
    anss.push_back(uttor);
  }
  for (auto z : anss) cout << z << "\n";
}
bool nroot(int x) { return x == t[t[x].fa].ch[0] || x == t[t[x].fa].ch[1]; }
void rotate(int x) {
  int y = t[x].fa;
  int z = t[y].fa;
  int k = x == t[y].ch[1];
  if (nroot(y)) t[z].ch[y == t[z].ch[1]] = x;
  t[x].fa = z;
  t[y].ch[k] = t[x].ch[k ^ 1];
  t[t[x].ch[k ^ 1]].fa = y;
  t[x].ch[k ^ 1] = y;
  t[y].fa = x;
  pushup(y);
  pushup(x);
}
void Splay(int x) {
  int u = x;
  sta[++top] = x;
  while (nroot(u)) sta[++top] = u = t[u].fa;
  while (top) pushdown(sta[top--]);
  while (nroot(x)) {
    int y = t[x].fa;
    int z = t[y].fa;
    if (nroot(y)) (x == t[y].ch[1]) ^ (y == t[z].ch[1]) ? rotate(x) : rotate(y);
    rotate(x);
  }
}
void access(int x) {
  for (int y = 0; x; x = t[y = x].fa) {
    Splay(x);
    t[x].vir += t[t[x].ch[1]].siz;
    t[x].ch[1] = y;
    t[x].vir -= t[t[x].ch[1]].siz;
    pushup(x);
  }
}
void makeroot(int x) {
  access(x);
  Splay(x);
  reverse(x);
}
void cut(int x, int y) {
  makeroot(x);
  access(y);
  Splay(y);
  t[x].fa = t[y].ch[0] = 0;
  pushup(y);
}
void split(int x, int y) {
  makeroot(x);
  access(y);
  Splay(y);
}
void link(int x, int y) {
  makeroot(x);
  access(y);
  Splay(y);
  t[x].fa = y;
  t[y].vir += t[x].siz;
}
void reverse(int x) {
  swap(t[x].ch[0], t[x].ch[1]);
  t[x].rev ^= 1;
}
void pushup(int x) {
  t[x].siz = t[t[x].ch[0]].siz + t[t[x].ch[1]].siz + t[x].vir + 1;
}
void pushdown(int x) {
  if (t[x].rev) {
    reverse(t[x].ch[0]);
    reverse(t[x].ch[1]);
    t[x].rev = false;
  }
}
