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 MAXN = 150007;
struct LinkCutTree {
  struct Node {
    int L, R, P, lazyFlip;
    int PP;
    int splayTreeSubtree;
    long long nodeCount, sumSubtree;
    long long lazy1, lazy2_m, lazy2_c;
  };
  Node LCT[MAXN];
  void normalize(int u) {
    assert(u != -1);
    LCT[u].splayTreeSubtree = 1;
    if (LCT[u].L != -1) {
      LCT[LCT[u].L].P = u;
      LCT[u].splayTreeSubtree += LCT[LCT[u].L].splayTreeSubtree;
    }
    if (LCT[u].R != -1) {
      LCT[LCT[u].R].P = u;
      LCT[u].splayTreeSubtree += LCT[LCT[u].R].splayTreeSubtree;
    }
  }
  void setLeftChild(int p, int v) {
    LCT[p].L = v;
    normalize(p);
  }
  void setRightChild(int p, int v) {
    LCT[p].R = v;
    normalize(p);
  }
  void pushLazy(int u) {
    if (LCT[u].lazy1) {
      LCT[u].nodeCount += LCT[u].lazy1;
      if (LCT[u].L != -1) LCT[LCT[u].L].lazy1 += LCT[u].lazy1;
      if (LCT[u].R != -1) LCT[LCT[u].R].lazy1 += LCT[u].lazy1;
      LCT[u].lazy1 = 0;
    }
    if (LCT[u].lazy2_m != 0 || LCT[u].lazy2_c != 0) {
      int dan = 0;
      if (LCT[u].R != -1) dan = LCT[LCT[u].R].splayTreeSubtree;
      LCT[u].sumSubtree += LCT[u].lazy2_c + (dan + 1) * LCT[u].lazy2_m;
      if (LCT[u].L != -1) {
        LCT[LCT[u].L].lazy2_c += LCT[u].lazy2_c + (dan + 1) * LCT[u].lazy2_m;
        LCT[LCT[u].L].lazy2_m += LCT[u].lazy2_m;
      }
      if (LCT[u].R != -1) {
        LCT[LCT[u].R].lazy2_c += LCT[u].lazy2_c;
        LCT[LCT[u].R].lazy2_m += LCT[u].lazy2_m;
      }
      LCT[u].lazy2_m = LCT[u].lazy2_c = 0;
    }
    if (!LCT[u].lazyFlip) return;
    swap(LCT[u].L, LCT[u].R);
    LCT[u].lazyFlip = 0;
    if (LCT[u].L != -1) LCT[LCT[u].L].lazyFlip ^= 1;
    if (LCT[u].R != -1) LCT[LCT[u].R].lazyFlip ^= 1;
  }
  void make_tree(int v) {
    LCT[v].L = LCT[v].R = LCT[v].P = LCT[v].PP = -1;
    LCT[v].lazyFlip = 0;
    LCT[v].nodeCount = 1;
    LCT[v].sumSubtree = 1;
    LCT[v].lazy1 = 0;
    LCT[v].lazy2_m = 0;
    LCT[v].lazy2_c = 0;
    LCT[v].splayTreeSubtree = 1;
  }
  void rotate(int v) {
    if (LCT[v].P == -1) return;
    int p = LCT[v].P;
    int g = LCT[p].P;
    if (LCT[p].L == v) {
      setLeftChild(p, LCT[v].R);
      setRightChild(v, p);
    } else {
      setRightChild(p, LCT[v].L);
      setLeftChild(v, p);
    }
    LCT[v].P = g;
    if (g != -1) {
      if (LCT[g].L == p) {
        setLeftChild(g, v);
      } else {
        setRightChild(g, v);
      }
    }
    LCT[v].PP = LCT[p].PP;
    LCT[p].PP = -1;
  }
  void splay(int v) {
    pushLazy(v);
    while (LCT[v].P != -1) {
      int p = LCT[v].P;
      int g = LCT[p].P;
      if (g != -1) pushLazy(g);
      pushLazy(p);
      pushLazy(v);
      if (g == -1) {
        rotate(v);
      } else if ((LCT[p].L == v) == (LCT[g].L == p)) {
        rotate(p);
        rotate(v);
      } else {
        rotate(v);
        rotate(v);
      }
    }
  }
  int access(int v) {
    splay(v);
    if (LCT[v].R != -1) {
      LCT[LCT[v].R].PP = v;
      LCT[LCT[v].R].P = -1;
      setRightChild(v, -1);
    }
    int ret = v;
    while (LCT[v].PP != -1) {
      int w = LCT[v].PP;
      splay(w);
      if (LCT[w].PP == -1) ret = w;
      if (LCT[w].R != -1) {
        LCT[LCT[w].R].PP = w;
        LCT[LCT[w].R].P = -1;
      }
      LCT[v].PP = -1;
      setRightChild(w, v);
      splay(v);
    }
    return ret;
  }
  int find_root(int v) {
    access(v);
    int ret = v;
    while (LCT[ret].L != -1) {
      ret = LCT[ret].L;
      pushLazy(ret);
    }
    access(ret);
    return ret;
  }
  void link(int v, int w) {
    access(w);
    access(v);
    LCT[w].lazy1 += LCT[v].nodeCount;
    LCT[w].lazy2_c += LCT[v].sumSubtree;
    LCT[w].lazy2_m += LCT[v].nodeCount;
    setLeftChild(v, w);
    LCT[w].PP = -1;
  }
  void cut(int v, int w) {
    access(v);
    if (LCT[v].L != -1) {
      int l = LCT[v].L;
      LCT[LCT[v].L].P = -1;
      LCT[LCT[v].L].PP = -1;
      setLeftChild(v, -1);
      LCT[l].lazy1 -= LCT[v].nodeCount;
      LCT[l].lazy2_c -= LCT[v].sumSubtree;
      LCT[l].lazy2_m -= LCT[v].nodeCount;
    }
  }
  void make_root(int v) {
    access(v);
    int l = LCT[v].L;
    if (l != -1) {
      setLeftChild(v, -1);
      LCT[l].P = -1;
      LCT[l].PP = v;
      LCT[l].lazyFlip ^= 1;
    }
  }
  bool isConnected(int p, int q) { return find_root(p) == find_root(q); }
  int LCA(int p, int q) {
    access(p);
    return access(q);
  }
} lct;
int a[MAXN], ps[MAXN];
set<pair<int, int> > edges[4 * MAXN];
void addEdge(int u, int l, int r, int x, int y) {
  int ll = x, rr = y;
  if (ll > rr) swap(ll, rr);
  if (r < ll || rr < l) return;
  if (ll <= l && r <= rr) {
    edges[u].emplace(x, y);
    return;
  }
  int mid = (l + r) / 2;
  addEdge(u * 2, l, mid, x, y);
  addEdge(u * 2 + 1, mid + 1, r, x, y);
}
void removeEdge(int u, int l, int r, int x, int y) {
  int ll = x, rr = y;
  if (ll > rr) swap(ll, rr);
  if (r < ll || rr < l) return;
  if (ll <= l && r <= rr) {
    edges[u].erase(pair<int, int>(x, y));
    return;
  }
  int mid = (l + r) / 2;
  removeEdge(u * 2, l, mid, x, y);
  removeEdge(u * 2 + 1, mid + 1, r, x, y);
}
vector<pair<int, int> > cutEdges;
void extractEdges(int u, int l, int r, int idx) {
  cutEdges.insert(cutEdges.end(), edges[u].begin(), edges[u].end());
  if (l == r) return;
  int mid = (l + r) / 2;
  if (idx <= mid)
    extractEdges(u * 2, l, mid, idx);
  else
    extractEdges(u * 2 + 1, mid + 1, r, idx);
}
ostream &operator<<(ostream &out, const pair<int, int> &p) {
  return out << "(" << p.first << "," << p.second << ")";
}
void addRoot(int n, int i) {
  cutEdges.clear();
  extractEdges(1, 1, n, ps[i]);
  addEdge(1, 1, n, ps[i - 1], ps[i]);
  lct.link(ps[i - 1], ps[i]);
  if (!cutEdges.empty()) {
    sort(cutEdges.begin(), cutEdges.end(),
         [&](pair<int, int> p, pair<int, int> q) {
           return max(a[p.first], a[p.second]) > max(a[q.first], a[q.second]);
         });
    for (int k = 0; k < cutEdges.size(); k++) {
      lct.cut(cutEdges[k].first, cutEdges[k].second);
      removeEdge(1, 1, n, cutEdges[k].first, cutEdges[k].second);
      if (k > 0) {
        lct.link(cutEdges[k].first, cutEdges[k - 1].second);
        addEdge(1, 1, n, cutEdges[k].first, cutEdges[k - 1].second);
      }
    }
    lct.link(cutEdges[0].first, ps[i]);
    addEdge(1, 1, n, cutEdges[0].first, ps[i]);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) {
    lct.make_tree(i);
    ps[a[i]] = i;
  }
  for (int i = 1; i <= n; i++) {
    lct.access(ps[i]);
    cout << lct.LCT[ps[i]].sumSubtree << "\n";
    if (i + 1 <= n) addRoot(n, i + 1);
  }
  return 0;
}
