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>
#pragma GCC optimize("O2")
#pragma G++ optimize("O2")
using namespace std;
const int N = 666666;
const int M = 888888;
const int MOD = 1e9 + 7;
const int intINF = 1e9;
const long long llINF = 2e18;
const double pi = acos(-1.0);
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const double eps = 1e-10;
int read() {
  int v = 0, f = 1;
  char c = getchar();
  while (c < 48 || 57 < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
  return v * f;
}
long long readll() {
  long long v = 0, f = 1;
  char c = getchar();
  while (c < 48 || 57 < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
  return v * f;
}
unsigned long long readull() {
  long long v = 0, f = 1;
  char c = getchar();
  while (c < 48 || 57 < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
  return v * f;
}
void predo() {}
int a[N], pos[N], n;
void init() {
  n = read();
  for (int i = (int)1; i <= (int)n; i++) {
    a[i] = read();
    pos[a[i]] = i;
  }
}
long long ret;
int p, c, d;
struct beats {
  int len[N], cma[N], cmi[N], ma[N], ma2[N], mi[N], mi2[N], tma[N], tmi[N],
      ta[N];
  long long sum[N];
  void tagma(int x, int p) {
    tma[x] += p;
    if (ma[x] == mi[x]) {
      ma[x] += p;
      mi[x] = ma[x];
      sum[x] = 1ll * ma[x] * len[x];
      return;
    }
    ma[x] += p;
    if (cma[x] + cmi[x] == len[x]) mi2[x] += p;
    sum[x] += 1ll * p * cma[x];
  }
  void tagmi(int x, int p) {
    tmi[x] += p;
    if (ma[x] == mi[x]) {
      ma[x] += p;
      mi[x] = ma[x];
      sum[x] = 1ll * ma[x] * len[x];
      return;
    }
    mi[x] += p;
    if (cma[x] + cmi[x] == len[x]) ma2[x] += p;
    sum[x] += 1ll * p * cmi[x];
  }
  void taga(int x, int p) {
    ta[x] += p;
    ma[x] += p;
    mi[x] += p;
    if (ma2[x] != -intINF) ma2[x] += p;
    if (mi2[x] != intINF) mi2[x] += p;
    sum[x] += 1ll * p * len[x];
  }
  void pushdown(int x) {
    if (tma[x]) {
      if (ma[x << 1] > ma[x << 1 | 1])
        tagma(x << 1, tma[x]);
      else if (ma[x << 1] < ma[x << 1 | 1])
        tagma(x << 1 | 1, tma[x]);
      else {
        tagma(x << 1, tma[x]);
        tagma(x << 1 | 1, tma[x]);
      }
      tma[x] = 0;
    }
    if (tmi[x]) {
      if (mi[x << 1] < mi[x << 1 | 1])
        tagmi(x << 1, tmi[x]);
      else if (mi[x << 1] > mi[x << 1 | 1])
        tagmi(x << 1 | 1, tmi[x]);
      else {
        tagmi(x << 1, tmi[x]);
        tagmi(x << 1 | 1, tmi[x]);
      }
      tmi[x] = 0;
    }
    if (ta[x]) {
      taga(x << 1, ta[x]);
      taga(x << 1 | 1, ta[x]);
      ta[x] = 0;
    }
  }
  void pushup(int x) {
    len[x] = len[x << 1] + len[x << 1 | 1];
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
    if (ma[x << 1] > ma[x << 1 | 1]) {
      ma[x] = ma[x << 1];
      ma2[x] = max(ma2[x << 1], ma[x << 1 | 1]);
      cma[x] = cma[x << 1];
    } else if (ma[x << 1] < ma[x << 1 | 1]) {
      ma[x] = ma[x << 1 | 1];
      ma2[x] = max(ma[x << 1], ma2[x << 1 | 1]);
      cma[x] = cma[x << 1 | 1];
    } else {
      ma[x] = ma[x << 1];
      ma2[x] = max(ma2[x << 1], ma2[x << 1 | 1]);
      cma[x] = cma[x << 1] + cma[x << 1 | 1];
    }
    if (mi[x << 1] < mi[x << 1 | 1]) {
      mi[x] = mi[x << 1];
      mi2[x] = min(mi2[x << 1], mi[x << 1 | 1]);
      cmi[x] = cmi[x << 1];
    } else if (mi[x << 1] > mi[x << 1 | 1]) {
      mi[x] = mi[x << 1 | 1];
      mi2[x] = min(mi[x << 1], mi2[x << 1 | 1]);
      cmi[x] = cmi[x << 1 | 1];
    } else {
      mi[x] = mi[x << 1];
      mi2[x] = min(mi2[x << 1], mi2[x << 1 | 1]);
      cmi[x] = cmi[x << 1] + cmi[x << 1 | 1];
    }
  }
  void build(int x, int a, int b) {
    if (a == b) {
      sum[x] = 0;
      ma[x] = ma2[x] = -intINF;
      mi[x] = mi2[x] = intINF;
      cma[x] = cmi[x] = 0;
      return;
    }
    int mid = (a + b) >> 1;
    build(x << 1, a, mid);
    build(x << 1 | 1, mid + 1, b);
    pushup(x);
  }
  void update(int x, int a, int b) {
    if (c <= a && b <= d) {
      taga(x, p);
      return;
    }
    pushdown(x);
    int mid = (a + b) >> 1;
    if (c <= mid) update(x << 1, a, mid);
    if (d > mid) update(x << 1 | 1, mid + 1, b);
    pushup(x);
  }
  void cmax(int x, int a, int b) {
    if (c <= a && b <= d) {
      if (mi[x] >= p) return;
      if (mi2[x] > p) {
        tagmi(x, p - mi[x]);
        return;
      }
    }
    pushdown(x);
    int mid = (a + b) >> 1;
    if (c <= mid) cmax(x << 1, a, mid);
    if (d > mid) cmax(x << 1 | 1, mid + 1, b);
    pushup(x);
  }
  void cmin(int x, int a, int b) {
    if (c <= a && b <= d) {
      if (ma[x] <= p) return;
      if (ma2[x] < p) {
        tagma(x, p - ma[x]);
        return;
      }
    }
    pushdown(x);
    int mid = (a + b) >> 1;
    if (c <= mid) cmin(x << 1, a, mid);
    if (d > mid) cmin(x << 1 | 1, mid + 1, b);
    pushup(x);
  }
  void change(int a, int b, int c, int y, int x) {
    if (a == b) {
      ma[x] = mi[x] = sum[x] = y, ma2[x] = -intINF, mi2[x] = intINF;
      cma[x] = cmi[x] = 1;
      len[x] = 1;
      return;
    }
    pushdown(x);
    int mid = (a + b) >> 1;
    if (c <= mid)
      change(a, mid, c, y, x << 1);
    else
      change(mid + 1, b, c, y, x << 1 | 1);
    pushup(x);
  }
} t1, t2;
int t[N];
int query(int x) {
  int res = 0;
  while (x) {
    res += t[x];
    x -= x & (-x);
  }
  return res;
}
void add(int x, int y) {
  while (x <= n) {
    t[x] += y;
    x += x & (-x);
  }
}
void solve() {
  t1.build(1, 1, n);
  t2.build(1, 1, n);
  for (int i = (int)1; i <= (int)n; i++) {
    t1.change(1, n, pos[i], 1, 1);
    t2.change(1, n, pos[i], i, 1);
    int m = query(pos[i]) + 1;
    add(pos[i], 1);
    c = pos[i] + 1, d = n, p = 1;
    if (c <= d) {
      t1.update(1, 1, n);
      t2.update(1, 1, n);
    }
    c = 1, d = pos[i] - 1, p = m - 1;
    if (c <= d) t2.cmin(1, 1, n);
    c = pos[i] + 1, d = n, p = m + 1;
    if (c <= d) t1.cmax(1, 1, n);
    long long ans = t2.sum[1] - t1.sum[1] + i;
    printf("%lld\n", ans);
  }
}
int main() {
  predo();
  int cas = 1;
  while (cas--) {
    init();
    solve();
  }
  return 0;
}
