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 = 150005;
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());
template <class T, int... Ns>
struct BIT {
  T val = 0;
  void upd(T v) { val += v; }
  T query() { return val; }
};
template <class T, int N, int... Ns>
struct BIT<T, N, Ns...> {
  BIT<T, Ns...> bit[N + 1];
  template <typename... Args>
  void upd(int pos, Args... args) {
    for (; pos <= N; pos += (pos & -pos)) bit[pos].upd(args...);
  }
  template <typename... Args>
  T sum(int r, Args... args) {
    T res = 0;
    for (; r; r -= (r & -r)) res += bit[r].query(args...);
    return res;
  }
  template <typename... Args>
  T query(int l, int r, Args... args) {
    return sum(r, args...) - sum(l - 1, args...);
  }
};
BIT<int, MX> nonNull, maxL, cool;
int n, pos[MX], lazy[1 << 19];
pair<pair<int, int>, pair<int, int> > mx[1 << 19];
long long ans[MX];
vector<int> a;
long long cur = 0;
pair<int, int> operator+(const pair<int, int>& l, const pair<int, int>& r) {
  if (l.first != r.first) return max(l, r);
  return {l.first, l.second + r.second};
}
pair<pair<int, int>, pair<int, int> > operator+(
    const pair<pair<int, int>, pair<int, int> >& l,
    const pair<pair<int, int>, pair<int, int> >& r) {
  if (l.first.first == r.first.first) {
    return {l.first + r.first, l.second + r.second};
  } else if (l.first > r.first) {
    return {l.first, l.second + r.first};
  }
  return {r.first, r.second + l.first};
}
void pull(int ind) { mx[ind] = mx[2 * ind] + mx[2 * ind + 1]; }
void push(int ind, int L, int R) {
  ckmin(mx[ind].first.first, lazy[ind]);
  if (L != R) {
    for (int i = (0); i < (2); ++i) ckmin(lazy[2 * ind + i], lazy[ind]);
  }
  lazy[ind] = MOD;
}
int getMaxL(int p, int ind, int L, int R) {
  push(ind, L, R);
  if (L == R) return mx[ind].first.first;
  int M = (L + R) / 2;
  if (p <= M) return getMaxL(p, 2 * ind, L, M);
  return getMaxL(p, 2 * ind + 1, M + 1, R);
}
void upd(int p, int v, int ind, int L, int R) {
  push(ind, L, R);
  if (p < L || R < p) return;
  if (L == R) {
    mx[ind] = {{v, 1}, {-MOD, 0}};
    return;
  }
  int M = (L + R) / 2;
  upd(p, v, 2 * ind, L, M);
  upd(p, v, 2 * ind + 1, M + 1, R);
  pull(ind);
}
void setMin(int lo, int hi, int ind, int L, int R) {
  push(ind, L, R);
  if (hi < L || R < lo) return;
  if (lo <= L && R <= hi && mx[ind].second.first <= hi) {
    if (mx[ind].first.first > hi) {
      int cnt = mx[ind].first.second;
      cur -= cnt * cool.query(hi + 1, mx[ind].first.first);
      maxL.upd(mx[ind].first.first, -cnt);
      maxL.upd(hi, cnt);
      lazy[ind] = hi;
      push(ind, L, R);
    }
    return;
  }
  int M = (L + R) / 2;
  setMin(lo, hi, 2 * ind, L, M);
  setMin(lo, hi, 2 * ind + 1, M + 1, R);
  pull(ind);
}
void rem(int p) {
  if (!nonNull.query(p, p)) return;
  int r = getMaxL(p, 1, 1, n);
  cur -= cool.query(p, r);
  nonNull.upd(p, -1);
  maxL.upd(r, -1);
  upd(p, -MOD, 1, 1, n);
}
void ad(int p) {
  cool.upd(p, 1);
  cur += maxL.query(p, n) - nonNull.query(p + 1, n);
  rem(p);
  if (p + 1 <= n) {
    rem(p + 1);
    cur += cool.query(p + 1, n);
    nonNull.upd(p + 1, 1);
    maxL.upd(n, 1);
    upd(p + 1, n, 1, 1, n);
  }
  setMin(2, p - 1, 1, 1, n);
}
void clr() {
  for (int i = (1); i < (1 << 19); ++i) {
    mx[i] = {{-MOD, 0}, {-MOD, 0}};
    lazy[i] = MOD;
  }
  nonNull = maxL = cool = BIT<int, MX>();
}
int main() {
  re(n);
  a.resize(n);
  re(a);
  if (n == 1) {
    ps(1);
    exit(0);
  }
  for (int i = (0); i < (n); ++i) pos[a[i]] = i + 1;
  for (int i = (1); i < (n + 1); ++i) ans[i] = i;
  clr();
  for (int i = (1); i < (n + 1); ++i) {
    ad(pos[i]);
    ans[i] += cur;
  }
  clr();
  cur = 0;
  for (int i = (1); i < (n + 1); ++i) pos[i] = n + 1 - pos[i];
  for (int i = (1); i < (n + 1); ++i) {
    ad(pos[i]);
    ans[i] += cur;
  }
  for (int i = (1); i < (n + 1); ++i) ps(ans[i]);
}
