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 std::make_pair;
template <typename T>
inline T read() {
  T x = 0;
  char ch = std::getchar();
  bool f = 0;
  while (!std::isdigit(ch)) {
    f = (ch == '-');
    ch = std::getchar();
  }
  while (std::isdigit(ch)) {
    x = x * 10 + (ch - '0');
    ch = std::getchar();
  }
  return f ? -x : x;
}
template <typename T>
void print(T x) {
  if (x < 0) {
    x = -x;
    std::putchar('-');
  }
  if (x < 10) {
    std::putchar(x + 48);
    return;
  }
  print<T>(x / 10);
  std::putchar(x % 10 + 48);
  return;
}
namespace Solution {
using std::cin;
using std::cout;
using std::deque;
using std::endl;
using std::map;
using std::pair;
using std::queue;
using std::set;
using std::vector;
const int N = 150001, INF = 0x3f3f3f3f;
int n, a[N], mp[N];
namespace BIT {
int Sc[N];
void Add(int x) {
  while (x <= n) Sc[x]++, x += x & -x;
}
int Sum(int x) {
  int res = 0;
  while (x) res += Sc[x], x -= x & -x;
  return res;
}
}  // namespace BIT
inline int ls(int k) { return k << 1; }
inline int rs(int k) { return k << 1 | 1; }
class SGTL {
 public:
  struct Node {
    int l, r, mx, se, num, mxtag, setag, F;
    long long sum;
  } elvahs[N * 4];
  inline void Up(int k) {
    if (!elvahs[ls(k)].F) {
      elvahs[k].mx = elvahs[rs(k)].mx;
      elvahs[k].se = elvahs[rs(k)].se;
      elvahs[k].num = elvahs[rs(k)].num;
      elvahs[k].sum = elvahs[rs(k)].sum;
      elvahs[k].F = elvahs[rs(k)].F;
    } else if (!elvahs[rs(k)].F) {
      elvahs[k].mx = elvahs[ls(k)].mx;
      elvahs[k].se = elvahs[ls(k)].se;
      elvahs[k].num = elvahs[ls(k)].num;
      elvahs[k].sum = elvahs[ls(k)].sum;
      elvahs[k].F = elvahs[ls(k)].F;
    } else {
      elvahs[k].mx = std::max(elvahs[ls(k)].mx, elvahs[rs(k)].mx);
      elvahs[k].se = std::max(elvahs[ls(k)].se, elvahs[rs(k)].se);
      elvahs[k].sum = elvahs[ls(k)].sum + elvahs[rs(k)].sum;
      if (elvahs[ls(k)].mx == elvahs[rs(k)].mx)
        elvahs[k].num = elvahs[ls(k)].num + elvahs[rs(k)].num;
      else
        elvahs[k].se = std::max(elvahs[k].se,
                                std::min(elvahs[ls(k)].mx, elvahs[rs(k)].mx)),
        elvahs[k].num = elvahs[ls(k)].mx > elvahs[rs(k)].mx ? elvahs[ls(k)].num
                                                            : elvahs[rs(k)].num;
      elvahs[k].F = elvahs[ls(k)].F + elvahs[rs(k)].F;
    }
    return;
  }
  inline void PutTag(int k, int x, int y) {
    elvahs[k].mx += x;
    elvahs[k].se += y;
    elvahs[k].mxtag += x;
    elvahs[k].setag += y;
    elvahs[k].sum +=
        1LL * (elvahs[k].F - elvahs[k].num) * y + 1LL * elvahs[k].num * x;
    return;
  }
  void Down(int k) {
    int mx = -INF;
    if (elvahs[ls(k)].F) mx = elvahs[ls(k)].mx;
    if (elvahs[rs(k)].F) mx = std::max(mx, elvahs[rs(k)].mx);
    if (elvahs[ls(k)].F) {
      if (elvahs[ls(k)].mx == mx)
        PutTag(ls(k), elvahs[k].mxtag, elvahs[k].setag);
      else
        PutTag(ls(k), elvahs[k].setag, elvahs[k].setag);
    }
    if (elvahs[rs(k)].F) {
      if (elvahs[rs(k)].mx == mx)
        PutTag(rs(k), elvahs[k].mxtag, elvahs[k].setag);
      else
        PutTag(rs(k), elvahs[k].setag, elvahs[k].setag);
    }
    elvahs[k].mxtag = elvahs[k].setag = 0;
    return;
  }
  void Build(int k, int l, int r) {
    elvahs[k].l = l;
    elvahs[k].r = r;
    if (l == r) return;
    int mid = l + r >> 1;
    Build(ls(k), l, mid);
    Build(rs(k), mid + 1, r);
    return;
  }
  void Modify1(int k, int pos, int x) {
    if (elvahs[k].l == elvahs[k].r) {
      elvahs[k].sum = elvahs[k].mx = x;
      elvahs[k].se = -INF;
      elvahs[k].F = elvahs[k].num = 1;
      return;
    }
    Down(k);
    int mid = elvahs[k].l + elvahs[k].r >> 1;
    pos <= mid ? Modify1(ls(k), pos, x) : Modify1(rs(k), pos, x);
    return Up(k);
  }
  void Modify2(int k, int l, int r) {
    if (!elvahs[k].F) return;
    if (l <= elvahs[k].l && elvahs[k].r <= r) return PutTag(k, 1, 1);
    Down(k);
    int mid = elvahs[k].l + elvahs[k].r >> 1;
    if (l <= mid) Modify2(ls(k), l, r);
    if (mid < r) Modify2(rs(k), l, r);
    return Up(k);
  }
  void Modify3(int k, int l, int r, int x) {
    if (!elvahs[k].F || elvahs[k].mx <= x) return;
    if (l <= elvahs[k].l && elvahs[k].r <= r && elvahs[k].se < x)
      return PutTag(k, x - elvahs[k].mx, 0);
    Down(k);
    int mid = elvahs[k].l + elvahs[k].r >> 1;
    if (l <= mid) Modify3(ls(k), l, r, x);
    if (mid < r) Modify3(rs(k), l, r, x);
    return Up(k);
  }
} R;
class SGTR {
 public:
  struct Node {
    int l, r, mn, se, num, mntag, setag, F;
    long long sum;
  } elvahs[N * 4];
  inline void Up(int k) {
    if (!elvahs[ls(k)].F) {
      elvahs[k].mn = elvahs[rs(k)].mn;
      elvahs[k].se = elvahs[rs(k)].se;
      elvahs[k].num = elvahs[rs(k)].num;
      elvahs[k].sum = elvahs[rs(k)].sum;
      elvahs[k].F = elvahs[rs(k)].F;
    } else if (!elvahs[rs(k)].F) {
      elvahs[k].mn = elvahs[ls(k)].mn;
      elvahs[k].se = elvahs[ls(k)].se;
      elvahs[k].num = elvahs[ls(k)].num;
      elvahs[k].sum = elvahs[ls(k)].sum;
      elvahs[k].F = elvahs[ls(k)].F;
    } else {
      elvahs[k].mn = std::min(elvahs[ls(k)].mn, elvahs[rs(k)].mn);
      elvahs[k].se = std::min(elvahs[ls(k)].se, elvahs[rs(k)].se);
      elvahs[k].sum = elvahs[ls(k)].sum + elvahs[rs(k)].sum;
      if (elvahs[ls(k)].mn == elvahs[rs(k)].mn)
        elvahs[k].num = elvahs[ls(k)].num + elvahs[rs(k)].num;
      else
        elvahs[k].se = std::min(elvahs[k].se,
                                std::max(elvahs[ls(k)].mn, elvahs[rs(k)].mn)),
        elvahs[k].num = elvahs[ls(k)].mn < elvahs[rs(k)].mn ? elvahs[ls(k)].num
                                                            : elvahs[rs(k)].num;
      elvahs[k].F = elvahs[ls(k)].F + elvahs[rs(k)].F;
    }
    return;
  }
  inline void PutTag(int k, int x, int y) {
    elvahs[k].mn += x;
    elvahs[k].se += y;
    elvahs[k].mntag += x;
    elvahs[k].setag += y;
    elvahs[k].sum +=
        1LL * (elvahs[k].F - elvahs[k].num) * y + 1LL * elvahs[k].num * x;
    return;
  }
  void Down(int k) {
    int mn = INF;
    if (elvahs[ls(k)].F) mn = elvahs[ls(k)].mn;
    if (elvahs[rs(k)].F) mn = std::min(mn, elvahs[rs(k)].mn);
    if (elvahs[ls(k)].F) {
      if (elvahs[ls(k)].mn == mn)
        PutTag(ls(k), elvahs[k].mntag, elvahs[k].setag);
      else
        PutTag(ls(k), elvahs[k].setag, elvahs[k].setag);
    }
    if (elvahs[rs(k)].F) {
      if (elvahs[rs(k)].mn == mn)
        PutTag(rs(k), elvahs[k].mntag, elvahs[k].setag);
      else
        PutTag(rs(k), elvahs[k].setag, elvahs[k].setag);
    }
    elvahs[k].mntag = elvahs[k].setag = 0;
    return;
  }
  void Build(int k, int l, int r) {
    elvahs[k].l = l;
    elvahs[k].r = r;
    if (l == r) return;
    int mid = l + r >> 1;
    Build(ls(k), l, mid);
    Build(rs(k), mid + 1, r);
    return;
  }
  void Modify1(int k, int pos, int x) {
    if (elvahs[k].l == elvahs[k].r) {
      elvahs[k].sum = elvahs[k].mn = x;
      elvahs[k].se = INF;
      elvahs[k].F = elvahs[k].num = 1;
      return;
    }
    Down(k);
    int mid = elvahs[k].l + elvahs[k].r >> 1;
    pos <= mid ? Modify1(ls(k), pos, x) : Modify1(rs(k), pos, x);
    return Up(k);
  }
  void Modify2(int k, int l, int r) {
    if (!elvahs[k].F) return;
    if (l <= elvahs[k].l && elvahs[k].r <= r) return PutTag(k, 1, 1);
    Down(k);
    int mid = elvahs[k].l + elvahs[k].r >> 1;
    if (l <= mid) Modify2(ls(k), l, r);
    if (mid < r) Modify2(rs(k), l, r);
    return Up(k);
  }
  void Modify3(int k, int l, int r, int x) {
    if (!elvahs[k].F || elvahs[k].mn >= x) return;
    if (l <= elvahs[k].l && elvahs[k].r <= r && elvahs[k].se > x)
      return PutTag(k, x - elvahs[k].mn, 0);
    Down(k);
    int mid = elvahs[k].l + elvahs[k].r >> 1;
    if (l <= mid) Modify3(ls(k), l, r, x);
    if (mid < r) Modify3(rs(k), l, r, x);
    return Up(k);
  }
} L;
void Fakemain() {
  n = read<int>();
  for (int i = 1; i <= n; ++i) mp[a[i] = read<int>()] = i;
  L.Build(1, 1, n);
  R.Build(1, 1, n);
  for (int i = 1; i <= n; ++i) {
    int p = mp[i], q = BIT::Sum(p) + 1;
    if (p > 1) R.Modify3(1, 1, p - 1, q - 1);
    if (p < n)
      L.Modify2(1, p + 1, n), R.Modify2(1, p + 1, n),
          L.Modify3(1, p + 1, n, q + 1);
    L.Modify1(1, p, 1);
    R.Modify1(1, p, i);
    BIT::Add(p);
    print<long long>(i + R.elvahs[1].sum - L.elvahs[1].sum), putchar('\n');
  }
  return;
}
}  // namespace Solution
int main(int argc, char* argv[]) {
  Solution::Fakemain();
  return 0;
}
