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(3)
using namespace std;
const int P = 998244353;
const int INF = 0x3f3f3f3f;
const long long INFLL = 0x3f3f3f3f3f3f3f3fll;
const int N = 1e6 + 5;
inline void max24(int &x, int &y, int a, int b, int c, int d) {
  if (a < c) swap(a, c);
  x = a;
  y = max(b, d);
  if (a != c) y = max(c, y);
}
struct node {
  int l, r;
  int max, s_max;
  int cnt_max, tag_max;
  int cnt_ava, tag_add;
  long long sum;
  node *lson, *rson;
  void mark_max(int val) {
    if (val >= max) return;
    sum += 1ll * cnt_max * (val - max);
    tag_max = max = val;
  }
  void mark_add(int val) {
    if (val == 0) return;
    sum += val * cnt_ava;
    max += val, s_max += val;
    tag_add += val, tag_max += val;
  }
  void push_down() {
    lson->mark_add(tag_add), lson->mark_max(tag_max);
    rson->mark_add(tag_add), rson->mark_max(tag_max);
    tag_max = INF, tag_add = 0;
  }
  void update() {
    push_down();
    sum = lson->sum + rson->sum;
    cnt_ava = lson->cnt_ava + rson->cnt_ava;
    max24(max, s_max, lson->max, lson->s_max, rson->max, rson->s_max);
    cnt_max = 0;
    if (max == lson->max) cnt_max += lson->cnt_max;
    if (max == rson->max) cnt_max += rson->cnt_max;
  }
} pool[2 * N], *root;
int n, m, top = -1;
int a[N];
void B_T(node *now, int l, int r) {
  now->l = l, now->r = r;
  now->tag_max = INF;
  if (l == r) {
    now->max = -INF, now->s_max = -INF - 1;
    now->cnt_max = 1;
    now->cnt_ava = now->sum = 0;
    return;
  }
  B_T(now->lson = &pool[++top], l, (l + r) / 2);
  B_T(now->rson = &pool[++top], (l + r) / 2 + 1, r);
  now->update();
}
void setmin(node *now, int l, int r, int val) {
  int lr = (now->l + now->r) >> 1, rl = lr + 1;
  if (now->l == l && now->r == r) {
    if (val > now->s_max)
      now->mark_max(val);
    else {
      now->push_down();
      setmin(now->lson, l, lr, val);
      setmin(now->rson, rl, r, val);
      now->update();
    }
    return;
  }
  now->push_down();
  if (r < rl)
    setmin(now->lson, l, r, val);
  else if (l > lr)
    setmin(now->rson, l, r, val);
  else
    setmin(now->lson, l, lr, val), setmin(now->rson, rl, r, val);
  now->update();
}
void setval(node *now, int id, int val) {
  if (now->l == now->r) {
    now->sum = now->max = val;
    now->cnt_ava = 1;
    return;
  }
  now->push_down();
  if (id <= (now->l + now->r) / 2)
    setval(now->lson, id, val);
  else
    setval(now->rson, id, val);
  now->update();
}
void addval(node *now, int l, int r, int val) {
  int lr = (now->l + now->r) >> 1, rl = lr + 1;
  if (now->l == l && now->r == r) {
    now->mark_add(val);
    return;
  }
  now->push_down();
  if (r < rl)
    addval(now->lson, l, r, val);
  else if (l > lr)
    addval(now->rson, l, r, val);
  else
    addval(now->lson, l, lr, val), addval(now->rson, rl, r, val);
  now->update();
}
long long query_sum(node *now, int l, int r) {
  int lr = (now->l + now->r) >> 1, rl = lr + 1;
  if (now->l == l && now->r == r) return now->sum;
  now->push_down();
  if (r < rl) return query_sum(now->lson, l, r);
  if (l > lr) return query_sum(now->rson, l, r);
  return query_sum(now->lson, l, lr) + query_sum(now->rson, rl, r);
}
int query_max(node *now, int l, int r) {
  int lr = (now->l + now->r) >> 1, rl = lr + 1;
  if (now->l == l && now->r == r) return now->max;
  now->push_down();
  if (r < rl) return query_max(now->lson, l, r);
  if (l > lr) return query_max(now->rson, l, r);
  return max(query_max(now->lson, l, lr), query_max(now->rson, rl, r));
}
int pos[N], vpos[N], C[N];
long long ans[N];
inline int lowbit(int x) { return x & -x; }
inline void BIT_add(int id, int val) {
  for (int i = id; i <= n; i += lowbit(i)) C[i] += val;
}
inline int BIT_query(int id) {
  int res = 0;
  for (int i = id; i > 0; i -= lowbit(i)) res += C[i];
  return res;
}
void init() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), pos[a[i]] = i;
  for (int i = 1; i <= n; i++) {
    BIT_add(pos[i], 1);
    vpos[i] = BIT_query(pos[i]);
  }
  B_T(root = &pool[++top], 1, n);
  for (int i = 1; i <= n; i++) {
    setval(root, pos[i], i);
    if (pos[i] - 1) setmin(root, 1, pos[i] - 1, vpos[i] - 1);
    if (pos[i] + 1 <= n) addval(root, pos[i] + 1, n, 1);
    ans[i] += root->sum;
  }
  memset(pool, 0, sizeof(pool));
  B_T(root = &pool[++top], 1, n);
  for (int i = 1; i <= n; i++) {
    setval(root, pos[i], n);
    if (pos[i] + 1 <= n) {
      addval(root, pos[i] + 1, n, -1);
      setmin(root, pos[i] + 1, n, n - vpos[i]);
    }
    ans[i] -= 1ll * n * i - root->sum;
  }
  for (int i = 1; i <= n; i++) printf("%lld\n", ans[i]);
}
int main() {
  init();
  return 0;
}
