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 N = 150010;
int n;
int a[N];
int p[N];
long long ans = 0;
struct fenwick {
  int fwt[N];
  int get(int x) {
    x += 5;
    int ans = 0;
    for (; x > 0; x -= x & -x) ans += fwt[x];
    return ans;
  }
  void upd(int x) {
    x += 5;
    for (; x < N; x += x & -x) fwt[x]++;
  }
} fwt;
bool operator!=(pair<int, int> a, pair<int, int> b) {
  return a.first != b.first;
}
namespace SegMin {
pair<int, int> maxsum(pair<int, int> u, pair<int, int> v) {
  if (u < v) swap(u, v);
  if (u.first == v.first) u.second += v.second;
  return u;
}
struct BeatMax {
  pair<int, int> a, b;
};
BeatMax operator+(BeatMax lhs, BeatMax rhs) {
  BeatMax ret;
  if (lhs.a < rhs.a) swap(lhs, rhs);
  ret = lhs;
  ret.a = maxsum(ret.a, rhs.a);
  ret.b = maxsum(ret.b, rhs.b);
  if (rhs.a != ret.a) ret.b = maxsum(ret.b, rhs.a);
  return ret;
}
int lazymin[N << 3];
BeatMax treemin[N << 2];
void build(int x, int l, int r) {
  lazymin[x] = N;
  if (l == r) {
    treemin[x].a = {-1, 1};
    treemin[x].b = {-1, 0};
    return;
  }
  build((x << 1), l, ((l + r) >> 1));
  build(((x << 1) | 1), ((l + r) >> 1) + 1, r);
  treemin[x] = treemin[(x << 1)] + treemin[((x << 1) | 1)];
}
void applymin(int x, long long add = 0) {
  if (lazymin[x] >= treemin[x].a.first) {
    lazymin[x] = N;
    return;
  }
  if (treemin[x].b.first < lazymin[x]) {
    ans -= add * treemin[x].a.second * fwt.get(treemin[x].a.first);
    treemin[x].a.first = lazymin[x];
    ans += add * treemin[x].a.second * fwt.get(treemin[x].a.first);
  }
  lazymin[(x << 1)] = min(lazymin[(x << 1)], lazymin[x]);
  lazymin[((x << 1) | 1)] = min(lazymin[((x << 1) | 1)], lazymin[x]);
  lazymin[x] = N;
}
void upd(int x, int l, int r, int u, int v, int val) {
  applymin(x);
  if (val >= treemin[x].a.first) return;
  if (l > v || r < u) return;
  if (l >= u && r <= v) {
    if (treemin[x].b.first < val) {
      lazymin[x] = val;
      applymin(x, 1);
      return;
    }
  }
  upd((x << 1), l, ((l + r) >> 1), u, v, val);
  upd(((x << 1) | 1), ((l + r) >> 1) + 1, r, u, v, val);
  treemin[x] = treemin[(x << 1)] + treemin[((x << 1) | 1)];
}
void modify(int x, int l, int r, int pos, int val) {
  applymin(x);
  if (l == r) {
    treemin[x].a = {val, 1};
    treemin[x].b = {-1, 0};
    return;
  }
  if (pos <= ((l + r) >> 1))
    modify((x << 1), l, ((l + r) >> 1), pos, val);
  else
    modify(((x << 1) | 1), ((l + r) >> 1) + 1, r, pos, val);
  applymin((x << 1));
  applymin(((x << 1) | 1));
  treemin[x] = treemin[(x << 1)] + treemin[((x << 1) | 1)];
}
void query(int x, int l, int r, int pos) {
  applymin(x);
  if (l == r) {
    cout << treemin[x].a.first << " ";
    return;
  }
  if (pos <= ((l + r) >> 1))
    query((x << 1), l, ((l + r) >> 1), pos);
  else
    query(((x << 1) | 1), ((l + r) >> 1) + 1, r, pos);
}
}  // namespace SegMin
namespace SegMax {
pair<int, int> minsum(pair<int, int> u, pair<int, int> v) {
  if (u > v) swap(u, v);
  if (u.first == v.first) u.second += v.second;
  return u;
}
struct BeatMin {
  pair<int, int> a, b;
};
BeatMin operator+(BeatMin lhs, BeatMin rhs) {
  BeatMin ret;
  if (lhs.a > rhs.a) swap(lhs, rhs);
  ret = lhs;
  ret.a = minsum(ret.a, rhs.a);
  ret.b = minsum(ret.b, rhs.b);
  if (rhs.a != ret.a) ret.b = minsum(ret.b, rhs.a);
  return ret;
}
int lazymax[N << 3];
BeatMin treemax[N << 2];
void build(int x, int l, int r) {
  lazymax[x] = -1;
  if (l == r) {
    treemax[x].a = {N, 1};
    treemax[x].b = {N, 0};
    return;
  }
  build((x << 1), l, ((l + r) >> 1));
  build(((x << 1) | 1), ((l + r) >> 1) + 1, r);
  treemax[x] = treemax[(x << 1)] + treemax[((x << 1) | 1)];
}
void applymax(int x, long long add = 0) {
  if (lazymax[x] <= treemax[x].a.first) {
    lazymax[x] = -1;
    return;
  }
  if (treemax[x].b.first > lazymax[x]) {
    ans += add * treemax[x].a.second * fwt.get(treemax[x].a.first);
    treemax[x].a.first = lazymax[x];
    ans -= add * treemax[x].a.second * fwt.get(treemax[x].a.first);
  }
  lazymax[(x << 1)] = max(lazymax[(x << 1)], lazymax[x]);
  lazymax[((x << 1) | 1)] = max(lazymax[((x << 1) | 1)], lazymax[x]);
  lazymax[x] = -1;
}
void upd(int x, int l, int r, int u, int v, int val) {
  applymax(x);
  if (val <= treemax[x].a.first) return;
  if (l > v || r < u) return;
  if (l >= u && r <= v) {
    if (treemax[x].b.first > val) {
      lazymax[x] = val;
      applymax(x, 1);
      return;
    }
  }
  upd((x << 1), l, ((l + r) >> 1), u, v, val);
  upd(((x << 1) | 1), ((l + r) >> 1) + 1, r, u, v, val);
  treemax[x] = treemax[(x << 1)] + treemax[((x << 1) | 1)];
}
void modify(int x, int l, int r, int pos, int val) {
  applymax(x);
  if (l == r) {
    treemax[x].a = {val, 1};
    treemax[x].b = {N, 0};
    return;
  }
  if (pos <= ((l + r) >> 1))
    modify((x << 1), l, ((l + r) >> 1), pos, val);
  else
    modify(((x << 1) | 1), ((l + r) >> 1) + 1, r, pos, val);
  applymax((x << 1));
  applymax(((x << 1) | 1));
  treemax[x] = treemax[(x << 1)] + treemax[((x << 1) | 1)];
}
void query(int x, int l, int r, int pos) {
  applymax(x);
  if (l == r) {
    cout << treemax[x].a.first << " ";
    return;
  }
  if (pos <= ((l + r) >> 1))
    query((x << 1), l, ((l + r) >> 1), pos);
  else
    query(((x << 1) | 1), ((l + r) >> 1) + 1, r, pos);
  treemax[x] = treemax[(x << 1)] + treemax[((x << 1) | 1)];
}
};  // namespace SegMax
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> a[i], --a[i];
  for (int i = 0; i < n; ++i) p[a[i]] = i;
  SegMin::build(1, 0, n - 1);
  SegMax::build(1, 0, n - 1);
  for (int i = 0; i < n; ++i) {
    ans += i + 1;
    int pos = p[i];
    if (pos > 0) SegMin::upd(1, 0, n - 1, 0, pos - 1, pos - 1);
    if (pos < n - 1) SegMax::upd(1, 0, n - 1, pos + 1, n - 1, pos);
    SegMax::modify(1, 0, n - 1, pos, -1);
    SegMin::modify(1, 0, n - 1, pos, n - 1);
    fwt.upd(pos);
    cout << ans << "\n";
  }
  return 0;
}
