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 MOD = 1e9 + 7;
const int MX = 1.5e5 + 5;
const long long INF = 1e18;
const long double PI = acos((long double)-1);
const int xd[4] = {1, 0, -1, 0}, yd[4] = {0, 1, 0, -1};
template <class T>
bool ckmin(T& a, const T& b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
int pc(int x) { return __builtin_popcount(x); }
namespace input {
template <class T>
void re(complex<T>& x);
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
void re(long double& x) {
  string t;
  re(t);
  x = stold(t);
}
template <class T, class... Ts>
void re(T& t, Ts&... ts) {
  re(t);
  re(ts...);
}
template <class T>
void re(complex<T>& x) {
  T a, b;
  re(a, b);
  x = {a, b};
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = (0); i < ((int)a.size()); ++i) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = (0); i < (SZ); ++i) re(a[i]);
}
}  // namespace input
using namespace input;
namespace output {
void pr(int x) { cout << x; }
void pr(long x) { cout << x; }
void pr(long long x) { cout << x; }
void pr(unsigned x) { cout << x; }
void pr(unsigned long x) { cout << x; }
void pr(unsigned long long x) { cout << x; }
void pr(float x) { cout << x; }
void pr(double x) { cout << x; }
void pr(long double x) { cout << x; }
void pr(char x) { cout << x; }
void pr(const char* x) { cout << x; }
void pr(const string& x) { cout << x; }
void pr(bool x) { pr(x ? "true" : "false"); }
template <class T>
void pr(const complex<T>& x) {
  cout << x;
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T>
void pr(const T& x);
template <class T, class... Ts>
void pr(const T& t, const Ts&... ts) {
  pr(t);
  pr(ts...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T>
void pr(const T& x) {
  pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? ", " : "", a), fst = 0;
  pr("}");
}
void ps() { pr("\n"); }
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(" ");
  ps(ts...);
}
void pc() { pr("]\n"); }
template <class T, class... Ts>
void pc(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(", ");
  pc(ts...);
}
}  // namespace output
using namespace output;
namespace io {
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void setIO(string second = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  if ((int)second.size()) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
}  // namespace io
using namespace io;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
typedef struct snode* sn;
struct snode {
  sn p, c[2];
  bool flip = 0;
  int id, val, sz;
  sn extra;
  int sub, vir = 0;
  snode(int _id, int v) {
    p = c[0] = c[1] = extra = NULL;
    id = _id, val = v;
    calc();
  }
  friend int getSz(sn x) { return x ? x->sz : 0; }
  friend int getSub(sn x) { return x ? x->sub : 0; }
  void prop() {
    if (!flip) return;
    swap(c[0], c[1]);
    for (int i = (0); i < (2); ++i)
      if (c[i]) c[i]->flip ^= 1;
    flip = 0;
  }
  long long totVal = 0, virVal = 0;
  void calc() {
    for (int i = (0); i < (2); ++i)
      if (c[i]) c[i]->prop();
    sz = 1 + getSz(c[0]) + getSz(c[1]);
    sub = 1 + getSub(c[0]) + getSub(c[1]) + vir;
    totVal = virVal + (c[0] ? c[0]->totVal : 0) + (c[1] ? c[1]->totVal : 0);
    totVal += (long long)(getSz(c[0]) + 1) * ((c[1] ? c[1]->sub : 0) + vir + 1);
  }
  int dir() {
    if (!p) return -2;
    for (int i = (0); i < (2); ++i)
      if (p->c[i] == this) return i;
    return -1;
  }
  bool isRoot() { return dir() < 0; }
  friend void setLink(sn x, sn y, int d) {
    if (y) y->p = x;
    if (d >= 0) x->c[d] = y;
  }
  void rot() {
    assert(!isRoot());
    int x = dir();
    sn pa = p;
    setLink(pa->p, this, pa->dir());
    setLink(pa, c[x ^ 1], x);
    setLink(this, pa, x ^ 1);
    pa->calc();
    calc();
  }
  void splay() {
    while (!isRoot() && !p->isRoot()) {
      p->p->prop(), p->prop(), prop();
      dir() == p->dir() ? p->rot() : rot();
      rot();
    }
    if (!isRoot()) p->prop(), prop(), rot();
    prop();
  }
  void access() {
    for (sn v = this, pre = NULL; v; v = v->p) {
      v->splay();
      if (pre) v->vir -= pre->sub, v->virVal -= pre->totVal;
      if (v->c[1]) v->vir += v->c[1]->sub, v->virVal += v->c[1]->totVal;
      v->c[1] = pre;
      v->calc();
      pre = v;
    }
    splay();
    assert(!c[1]);
  }
  void makeRoot() {
    access();
    flip ^= 1;
    prop();
    assert(!c[0]);
  }
  friend sn lca(sn x, sn y) {
    if (x == y) return x;
    x->access(), y->access();
    if (!x->p) return NULL;
    x->splay();
    return x->p ?: x;
  }
  friend bool connected(sn x, sn y) { return lca(x, y); }
  int distRoot() {
    access();
    return getSz(c[0]);
  }
  sn getRoot() {
    access();
    auto a = this;
    while (a->c[0]) a = a->c[0], a->prop();
    a->access();
    return a;
  }
  sn getPar(int b) {
    access();
    b = getSz(c[0]) - b;
    assert(b >= 0);
    auto a = this;
    while (1) {
      int z = getSz(a->c[0]);
      if (b == z) {
        a->access();
        return a;
      }
      if (b < z)
        a = a->c[0];
      else
        a = a->c[1], b -= z + 1;
      a->prop();
    }
  }
  void set(int v) {
    access();
    val = v;
    calc();
  }
  friend void link(sn x, sn y, bool force = 0) {
    assert(!connected(x, y));
    if (force)
      y->makeRoot();
    else {
      y->access();
      assert(!y->c[0]);
    }
    x->access();
    setLink(y, x, 0);
    y->calc();
  }
  friend void cut(sn y) {
    y->access();
    assert(y->c[0]);
    y->c[0]->p = NULL;
    y->c[0] = NULL;
    y->calc();
  }
  friend void cut(sn x, sn y) {
    x->makeRoot();
    y->access();
    assert(y->c[0] == x && !x->c[0] && !x->c[1]);
    cut(y);
  }
};
sn LCT[MX];
void setNex(sn a, sn b) {
  if (connected(a, b))
    a->extra = b;
  else
    link(b, a);
}
void delNex(sn a) {
  auto t = a->getRoot();
  if (t == a) {
    t->extra = NULL;
    return;
  }
  cut(a);
  assert(t->extra);
  if (!connected(t, t->extra)) link(t->extra, t), t->extra = NULL;
}
sn getPar(sn a, int b) {
  int d = a->distRoot();
  if (b <= d) return a->getPar(b);
  b -= d + 1;
  auto r = a->getRoot()->extra;
  assert(r);
  d = r->distRoot() + 1;
  return r->getPar(b % d);
}
template <class T>
struct RMQ {
  int level(int x) { return 31 - __builtin_clz(x); }
  vector<T> v;
  vector<vector<int> > jmp;
  int comb(int a, int b) {
    return v[a] == v[b] ? min(a, b) : (v[a] > v[b] ? a : b);
  }
  void init(const vector<T>& _v) {
    v = _v;
    jmp = {vector<int>((int)v.size())};
    iota(begin(jmp[0]), end(jmp[0]), 0);
    for (int j = 1; 1 << j <= (int)v.size(); ++j) {
      jmp.push_back(vector<int>((int)v.size() - (1 << j) + 1));
      for (int i = (0); i < ((int)jmp[j].size()); ++i)
        jmp[j][i] = comb(jmp[j - 1][i], jmp[j - 1][i + (1 << (j - 1))]);
    }
  }
  int index(int l, int r) {
    int d = level(r - l + 1);
    return comb(jmp[d][l], jmp[d][r - (1 << d) + 1]);
  }
  T query(int l, int r) { return v[index(l, r)]; }
};
int N, iA[MX];
long long ans[MX];
vector<int> A;
RMQ<int> R;
sn makeTree(int l, int r) {
  if (l > r) return NULL;
  int i = R.index(l, r);
  auto L = makeTree(l, i - 1);
  if (L) link(LCT[i], L);
  auto R = makeTree(i + 1, r);
  if (R) link(LCT[i], R);
  return LCT[i];
}
sn cur;
void process(sn x) {
  if (!x) return;
  sn a = x->c[0], b = x->c[1];
  if (a) a->p = NULL;
  if (b) b->p = NULL;
  x->c[0] = x->c[1] = NULL;
  x->calc();
  process(a);
  sn insert = cur;
  while (1) {
    int d = (x->val < insert->val);
    if (insert->c[d] == NULL) {
      setLink(insert, x, d);
      break;
    } else
      insert = insert->c[d];
  }
  x->splay();
  cur = x;
  process(b);
}
sn getLeft(sn x) {
  if (!x->c[0]) return x;
  return getLeft(x->c[0]);
}
int main() {
  setIO();
  re(N);
  A.resize(N);
  re(A);
  for (int i = (0); i < (N); ++i) iA[A[i]] = i;
  for (int i = (0); i < (N); ++i) LCT[i] = new snode(i, A[i]);
  R.init(A);
  makeTree(0, N - 1);
  set<int> vals;
  for (int i = (0); i < (N); ++i) vals.insert(i);
  for (int t = (N + 1) - 1; t >= (1); --t) {
    int i = iA[t];
    LCT[i]->access();
    if (LCT[i]->c[0]) {
      cout << "AH " << LCT[i]->val << " " << LCT[i]->c[0]->val << "\n";
      ps("ID", LCT[i]->c[0]->id);
    }
    assert(!LCT[i]->c[0]);
    ans[t] = LCT[i]->totVal;
    auto it = vals.erase(vals.find(i));
    sn l = NULL, r = NULL;
    LCT[i]->access();
    if (it != end(vals)) {
      r = LCT[*it];
      r->access();
      LCT[i]->access();
      r->splay();
      assert(r->p == LCT[i]);
      cut(getLeft(r));
    }
    LCT[i]->access();
    if (it != begin(vals)) {
      l = LCT[*prev(it)];
      l->access();
      LCT[i]->access();
      l->splay();
      assert(l->p == LCT[i]);
      cut(getLeft(l));
    }
    LCT[i]->access();
    if (!l || !r) continue;
    l->access(), r->access();
    assert(!l->c[1] && !r->c[1]);
    if (l->sz > r->sz) swap(l, r);
    cur = r;
    process(l);
  }
  for (int i = (1); i < (N + 1); ++i) ps(ans[i]);
}
