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 T>
bool vmin(T& a, T b) {
  return (a > b) ? (a = b, true) : (false);
}
template <typename T>
bool vmax(T& a, T b) {
  return (a < b) ? (a = b, true) : (false);
}
template <typename T>
T smax(T x) {
  return x;
}
template <typename T, typename... K>
T smax(T a, const K&... args) {
  return max(a, smax(args...));
}
template <typename T>
T smin(T x) {
  return x;
}
template <typename T, typename... K>
T smin(T a, const K&... args) {
  return min(a, smin(args...));
}
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& z) {
  os << "(" << z.first << ", " << z.second << ')';
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& a) {
  bool isfirst = true;
  os << "{";
  for (auto z : a) {
    if (!isfirst) {
      os << ", ";
    }
    os << z;
    isfirst = false;
  }
  os << '}';
  return os;
}
const int N = 150005;
typedef class Event {
 public:
  int op, p, v;
  Event(int op, int p, int v) : op(op), p(p), v(v) {}
  bool operator<(Event b) const { return p > b.p; }
} Event;
typedef class Fenwick {
 public:
  int n;
  vector<int> a;
  void init(int n) {
    this->n = n;
    a = vector<int>(n + 1, 0);
  }
  void add(int idx, int v) {
    for (; idx <= n; idx += (idx & (-idx))) a[idx] += v;
  }
  int query(int idx) {
    int rt = 0;
    for (; idx; idx -= (idx & (-idx))) rt += a[idx];
    return rt;
  }
  int query(int l, int r) { return query(r) - query(l - 1); }
} Fenwick;
int n;
int a[N];
long long ans[N];
void add(int l, int r, long long d) {
  ans[l] += d;
  ans[r + 1] -= d;
}
void dividing(int l, int r) {
  if (l == r) {
    ans[a[l]] += 1;
    return;
  }
  int mid = (l + r) >> 1;
  vector<int> stk;
  vector<int> tg;
  vector<Event> E;
  Fenwick fen;
  for (int i = r; i > mid; i--) E.emplace_back(0, a[i], i);
  int len = r - mid;
  set<int> S;
  S.insert(n + 1);
  for (int i = mid; i >= l; i--) {
    E.emplace_back(1, a[i], *S.upper_bound(a[i]));
    S.insert(a[i]);
  }
  sort(E.begin(), E.end());
  fen.init(len);
  for (int i = 1; i <= len; i++) fen.add(i, 1);
  for (auto it = E.begin(); it != E.end(); it++) {
    if ((*it).op == 0) {
      int p = (*it).v, q;
      int sum = 0;
      while (!stk.empty() && stk.back() > p) {
        q = stk.back();
        sum += tg.back();
        stk.pop_back(), tg.pop_back();
        add(a[q], (stk.empty()) ? (n) : (a[stk.back()] - 1),
            1ll * fen.query(q - mid - 1) * sum);
      }
      if (!tg.empty()) tg.back() += sum;
      stk.push_back(p);
      tg.push_back(0);
      fen.add(p - mid, -1);
    } else if ((*it).op == 1) {
      int ql = (*it).p, qr = (*it).v - 1;
      int L = 0, R = (signed)stk.size() - 1, Mid;
      while (L <= R) {
        Mid = (L + R) >> 1;
        if (a[stk[Mid]] > qr) {
          L = Mid + 1;
        } else {
          R = Mid - 1;
        }
      }
      if (L == (signed)stk.size()) {
        add(ql, qr, fen.query(len));
      } else {
        add(ql, a[stk.back()] - 1, fen.query(len));
        add(a[stk[L]], qr, fen.query(stk[L] - mid - 1));
        tg.back() += 1;
        tg[L] -= 1;
      }
    }
  }
  len = mid - l + 1;
  stk.clear(), tg.clear(), E.clear();
  for (int i = l; i <= mid; i++) E.emplace_back(0, a[i], i);
  S.clear();
  S.insert(n + 1);
  for (int i = mid + 1; i <= r; i++) {
    E.emplace_back(1, a[i], *S.upper_bound(a[i]));
    S.insert(a[i]);
  }
  sort(E.begin(), E.end());
  fen.init(len);
  for (int i = 1; i <= len; i++) fen.add(i, 1);
  for (auto it = E.begin(); it != E.end(); it++) {
    if ((*it).op == 0) {
      int p = (*it).v, q;
      int sum = 0;
      while (!stk.empty() && stk.back() < p) {
        q = stk.back();
        sum += tg.back();
        stk.pop_back(), tg.pop_back();
        add(a[q], (stk.empty()) ? (n) : (a[stk.back()] - 1),
            1ll * fen.query(mid - q) * sum);
      }
      if (!tg.empty()) tg.back() += sum;
      stk.push_back(p);
      tg.push_back(0);
      fen.add(mid - p + 1, -1);
    } else if ((*it).op == 1) {
      int ql = (*it).p, qr = (*it).v - 1;
      int L = 0, R = (signed)stk.size() - 1, Mid;
      while (L <= R) {
        Mid = (L + R) >> 1;
        if (a[stk[Mid]] > qr) {
          L = Mid + 1;
        } else {
          R = Mid - 1;
        }
      }
      if (L == (signed)stk.size()) {
        add(ql, qr, fen.query(len));
      } else {
        add(ql, a[stk.back()] - 1, fen.query(len));
        add(a[stk[L]], qr, fen.query(mid - stk[L]));
        tg.back() += 1;
        tg[L] -= 1;
      }
    }
  }
  dividing(l, mid);
  dividing(mid + 1, r);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
  }
  dividing(1, n);
  for (int i = 1; i <= n; i++) {
    printf("%lld\n", ans[i] += ans[i - 1]);
  }
  return 0;
}
