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;
using cat = long long;
struct fin {
  vector<int> T;
  fin(int N) : T(N + 1, 0) {}
  int lastone(int x) { return x & (x ^ (x - 1)); }
  void put(int pos, int val) {
    for (int i = pos + 1; i < (int)T.size(); i += lastone(i)) T[i] += val;
  }
  int get(int pos) {
    int ret = 0;
    for (int i = pos + 1; i; i -= lastone(i)) ret += T[i];
    return ret;
  }
};
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(10);
  int N;
  cin >> N;
  vector<int> A(N), pos(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    pos[--A[i]] = i;
  }
  vector<cat> ans(N, 0);
  for (int k = 0; k < 2; k++) {
    reverse(begin(A), end(A));
    for (int i = 0; i < N; i++) pos[A[i]] = i;
    fin F(N);
    constexpr int K = 300;
    int B = N / K + 1;
    vector<vector<pair<int, int> > > bl(B);
    vector<vector<int> > last_ids(B);
    vector<int> last_val(B), add(B, 0);
    vector<cat> sum(B, 0);
    for (int i = 0; i < N; i++) {
      int p = pos[i];
      int val = F.get(p);
      F.put(p, 1);
      int id = p / K;
      static vector<pair<int, int> > bl_low;
      bl_low.clear();
      static vector<pair<int, int> > bl_hi;
      bl_hi.clear();
      for (auto pp : bl[id]) {
        pp.first += add[id];
        if (pp.second < p)
          bl_low.push_back({min(pp.first, val), pp.second});
        else
          bl_hi.push_back({pp.first + 1, pp.second});
      }
      last_val[id] += add[id];
      for (auto x : last_ids[id]) {
        if (x < p)
          bl_low.push_back({min(last_val[id], val), x});
        else
          bl_hi.push_back({last_val[id] + 1, x});
      }
      bl[id].clear();
      merge(begin(bl_low), end(bl_low), begin(bl_hi), end(bl_hi),
            back_inserter(bl[id]));
      bl[id].push_back({i + 1, p});
      for (int j = (int)bl[id].size() - 2; j >= 0; j--) {
        if (bl[id][j].first > bl[id][j + 1].first)
          swap(bl[id][j], bl[id][j + 1]);
        else
          break;
      }
      last_ids[id].clear();
      add[id] = sum[id] = 0;
      for (auto pp : bl[id]) sum[id] += pp.first;
      for (int j = id + 1; j < B; j++) {
        add[j]++;
        sum[j] += last_ids[j].size() + bl[j].size();
      }
      for (int j = 0; j < id; j++) {
        int v = val - add[j];
        if (!last_ids[j].empty() && last_val[j] <= v) continue;
        sum[j] -= 1LL * (last_val[j] - v) * last_ids[j].size();
        last_val[j] = min(last_val[j], v);
        if (last_ids[j].empty()) {
          if (bl[j].empty()) continue;
          int x = bl[j].back().first;
          if (x < v) continue;
          sum[j] += v - x;
          last_val[j] = v;
          last_ids[j].push_back(bl[j].back().second);
          bl[j].pop_back();
        }
        while (!bl[j].empty()) {
          int x = bl[j].back().first;
          if (x < last_val[j]) break;
          sum[j] += last_val[j] - x;
          last_ids[j].push_back(bl[j].back().second);
          bl[j].pop_back();
        }
      }
      for (int j = 0; j <= N / K; j++) ans[i] += sum[j];
    }
  }
  for (int i = 0; i < N; i++) cout << ans[i] - (i + 1LL) * (i + 1) << "\n";
  return 0;
}
