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;
template <typename T1, typename T2>
void chkmin(T1 &x, T2 y) {
  if (x > y) x = y;
}
template <typename T1, typename T2>
void chkmax(T1 &x, T2 y) {
  if (x < y) x = y;
}
inline void debug(int x) { fprintf(stderr, "ycx has aked ioi %d times\n", x); }
namespace fastio {
char rbuf[1 << 23], *p1 = rbuf, *p2 = rbuf, wbuf[1 << 23], *p3 = wbuf;
inline char getc() {
  return p1 == p2 &&
                 (p2 = (p1 = rbuf) + fread(rbuf, 1, 1 << 23, stdin), p1 == p2)
             ? -1
             : *p1++;
}
inline void putc(char x) { (*p3++ = x); }
template <typename T>
void read(T &x) {
  x = 0;
  char c = getchar();
  T neg = 0;
  while (!isdigit(c)) neg |= !(c ^ '-'), c = getchar();
  while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  if (neg) x = (~x) + 1;
}
template <typename T>
void recursive_print(T x) {
  if (!x) return;
  recursive_print(x / 10);
  putc(x % 10 ^ 48);
}
template <typename T>
void print(T x) {
  if (!x) putc('0');
  if (x < 0) putc('-'), x = ~x + 1;
  recursive_print(x);
}
template <typename T>
void print(T x, char c) {
  if (!x) putc('0');
  if (x < 0) putc('-'), x = ~x + 1;
  recursive_print(x);
  putc(c);
}
void print_final() { fwrite(wbuf, 1, p3 - wbuf, stdout); }
}  // namespace fastio
const int MAXN = 1.5e5;
int n, p[MAXN + 5], ps[MAXN + 5];
struct node {
  int l, r, mx, smx, mxc, lz_add, lz_mx, c;
  long long sum;
} s[MAXN * 4 + 5];
void pushup(int k) {
  s[k].mx = max(s[k << 1].mx, s[k << 1 | 1].mx);
  if (s[k << 1].mx > s[k << 1 | 1].mx)
    s[k].smx = max(s[k << 1 | 1].mx, s[k << 1].smx);
  else if (s[k << 1].mx < s[k << 1 | 1].mx)
    s[k].smx = max(s[k << 1].mx, s[k << 1 | 1].smx);
  else
    s[k].smx = max(s[k << 1].smx, s[k << 1 | 1].smx);
  s[k].mxc = 0;
  if (s[k << 1].mx == s[k].mx) s[k].mxc += s[k << 1].mxc;
  if (s[k << 1 | 1].mx == s[k].mx) s[k].mxc += s[k << 1 | 1].mxc;
  s[k].sum = s[k << 1].sum + s[k << 1 | 1].sum;
  s[k].c = s[k << 1].c + s[k << 1 | 1].c;
}
void build(int k, int l, int r) {
  s[k].l = l;
  s[k].r = r;
  s[k].lz_mx = -1;
  if (l == r) return s[k].mx = 0, s[k].smx = -1, void();
  int mid = l + r >> 1;
  build(k << 1, l, mid);
  build(k << 1 | 1, mid + 1, r);
  pushup(k);
}
void pushdown(int k) {
  if (s[k].lz_add) {
    if (s[k << 1].mx != s[k].mx) {
      s[k << 1].sum += 1ll * s[k << 1].c * s[k].lz_add;
      if (~s[k << 1].lz_mx)
        s[k << 1].lz_mx += s[k].lz_add;
      else
        s[k << 1].lz_mx = s[k << 1].mx + s[k].lz_add;
      s[k << 1].mx += s[k].lz_add;
    } else {
      s[k << 1].sum += 1ll * (s[k << 1].c - s[k << 1].mxc) * s[k].lz_add;
    }
    s[k << 1].smx += s[k].lz_add;
    s[k << 1].lz_add += s[k].lz_add;
    if (s[k << 1 | 1].mx != s[k].mx) {
      s[k << 1 | 1].sum += 1ll * s[k << 1 | 1].c * s[k].lz_add;
      if (~s[k << 1 | 1].lz_mx)
        s[k << 1 | 1].lz_mx += s[k].lz_add;
      else
        s[k << 1 | 1].lz_mx = s[k << 1 | 1].mx + s[k].lz_add;
      s[k << 1 | 1].mx += s[k].lz_add;
    } else {
      s[k << 1 | 1].sum +=
          1ll * (s[k << 1 | 1].c - s[k << 1 | 1].mxc) * s[k].lz_add;
    }
    s[k << 1 | 1].smx += s[k].lz_add;
    s[k << 1 | 1].lz_add += s[k].lz_add;
    s[k].lz_add = 0;
  }
  if (~s[k].lz_mx) {
    int ori_mx = max(s[k << 1].mx, s[k << 1 | 1].mx);
    if (s[k << 1].mx == ori_mx) {
      s[k << 1].sum += 1ll * s[k << 1].mxc * (s[k].lz_mx - s[k << 1].mx);
      s[k << 1].lz_mx = s[k].lz_mx;
      s[k << 1].mx = s[k].lz_mx;
    }
    if (s[k << 1 | 1].mx == ori_mx) {
      s[k << 1 | 1].sum +=
          1ll * s[k << 1 | 1].mxc * (s[k].lz_mx - s[k << 1 | 1].mx);
      s[k << 1 | 1].lz_mx = s[k].lz_mx;
      s[k << 1 | 1].mx = s[k].lz_mx;
    }
    s[k].lz_mx = -1;
  }
}
void modify(int k, int l, int r, int x) {
  if (l > r) return;
  if (l <= s[k].l && s[k].r <= r) {
    if (x >= s[k].mx)
      return;
    else if (x > s[k].smx) {
      s[k].lz_mx = x;
      s[k].sum -= 1ll * s[k].mxc * (s[k].mx - x);
      s[k].mx = x;
      return;
    } else {
      int mid = (pushdown(k), l + r >> 1);
      modify(k << 1, l, mid, x);
      modify(k << 1 | 1, mid + 1, r, x);
      return pushup(k), void();
    }
    assert(0);
  }
  int mid = (pushdown(k), s[k].l + s[k].r >> 1);
  if (r <= mid)
    modify(k << 1, l, r, x);
  else if (l > mid)
    modify(k << 1 | 1, l, r, x);
  else
    modify(k << 1, l, mid, x), modify(k << 1 | 1, mid + 1, r, x);
  pushup(k);
}
void add(int k, int l, int r) {
  if (l > r) return;
  if (l <= s[k].l && s[k].r <= r) {
    s[k].sum += s[k].c;
    s[k].mx++;
    s[k].smx++;
    s[k].lz_add++;
    if (~s[k].lz_mx)
      s[k].lz_mx++;
    else
      s[k].lz_mx = s[k].mx;
    return;
  }
  int mid = (pushdown(k), s[k].l + s[k].r >> 1);
  if (r <= mid)
    add(k << 1, l, r);
  else if (l > mid)
    add(k << 1 | 1, l, r);
  else
    add(k << 1, l, mid), add(k << 1 | 1, mid + 1, r);
  pushup(k);
}
void make(int k, int p, int v) {
  if (s[k].l == s[k].r)
    return s[k].sum = s[k].mx = v, s[k].c = s[k].mxc = 1, void();
  int mid = (pushdown(k), s[k].l + s[k].r >> 1);
  return ((p <= mid) ? make(k << 1, p, v) : make(k << 1 | 1, p, v)), pushup(k),
         void();
}
void clear(int k) {
  s[k].c = s[k].lz_add = s[k].mx = s[k].mxc = s[k].sum = 0;
  s[k].lz_mx = s[k].smx = -1;
  if (s[k].l == s[k].r) return;
  clear(k << 1);
  clear(k << 1 | 1);
}
long long ans[MAXN + 5];
int t[MAXN + 5];
void turn(int x, int v) {
  for (int i = x; i <= n; i += (i & (-i))) t[i] += v;
}
int qry(int x) {
  int ret = 0;
  for (int i = x; i; i &= (i - 1)) ret += t[i];
  return ret;
}
int main() {
  scanf("%d", &n);
  build(1, 1, n);
  for (int i = 1; i <= n; i++) scanf("%d", &p[i]), ps[p[i]] = i;
  for (int i = 1, j = ps[1]; i <= n; i++, j = ps[i]) {
    modify(1, 1, j - 1, qry(j) + 1);
    add(1, j + 1, n);
    make(1, j, i + 1);
    turn(j, 1);
    ans[i] += s[1].sum;
  }
  clear(1);
  reverse(p + 1, p + n + 1);
  memset(t, 0, sizeof(t));
  for (int i = 1; i <= n; i++) ps[i] = n + 1 - ps[i];
  for (int i = 1, j = ps[1]; i <= n; i++, j = ps[i]) {
    modify(1, 1, j - 1, qry(j) + 1);
    add(1, j + 1, n);
    make(1, j, i + 1);
    turn(j, 1);
    ans[i] -= 1ll * i * (i + 1) - s[1].sum;
  }
  for (int i = 1; i <= n; i++) printf("%lld\n", ans[i] - i);
  return 0;
}
