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 double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0},  {0, -1},
                        {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
template <class T>
inline T abs1(T a) {
  return a < 0 ? -a : a;
}
template <typename t, typename t1>
t min1(t a, t1 b) {
  return a < b ? a : b;
}
template <typename t, typename... arg>
t min1(t a, arg... arr) {
  return min1(a, min1(arr...));
}
template <typename t, typename t1>
t max1(t a, t1 b) {
  return a > b ? a : b;
}
template <typename t, typename... arg>
t max1(t a, arg... arr) {
  return max1(a, max1(arr...));
}
inline int jud(double a, double b) {
  if (abs(a) < eps && abs(b) < eps)
    return 0;
  else if (abs1(a - b) / max(abs1(a), abs1(b)) < eps)
    return 0;
  if (a < b) return -1;
  return 1;
}
template <typename t>
inline int jud(t a, t b) {
  if (a < b) return -1;
  if (a == b) return 0;
  return 1;
}
template <typename it, typename t1>
inline int RangeFind(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1) {
  if (na == 0) return 0;
  int be = 0, en = na - 1;
  if (*a <= *(a + na - 1)) {
    if (f_lb == 0)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != 1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != -1)
          en = mid;
        else
          be = mid + 1;
      }
    if (f_small && jud(*(a + be), val) == 1) be--;
    if (!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if (f_lb)
      while (be < en) {
        int mid = (be + en + 1) / 2;
        if (jud(*(a + mid), val) != -1)
          be = mid;
        else
          en = mid - 1;
      }
    else
      while (be < en) {
        int mid = (be + en) / 2;
        if (jud(*(a + mid), val) != 1)
          en = mid;
        else
          be = mid + 1;
      }
    if (!f_small && jud(*(a + be), val) == -1) be--;
    if (f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}
template <class T>
inline T lowb(T num) {
  return num & (-num);
}
inline int bitnum(unsigned int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(unsigned long long nValue) {
  return __builtin_popcountll(nValue);
}
inline int bitnum(long long nValue) { return __builtin_popcountll(nValue); }
inline int bitmaxl(unsigned int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(int a) {
  if (a == 0) return 0;
  return 32 - __builtin_clz(a);
}
inline int bitmaxl(unsigned long long a) {
  if (a == 0) return 0;
  return 64 - __builtin_clzll(a);
}
inline int bitmaxl(long long a) {
  if (a == 0) return 0;
  return 64 - __builtin_clzll(a);
}
long long pow(long long n, long long m, long long mod = 0) {
  if (m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while (m) {
    if (m & 1) {
      ans *= k;
      if (mod) ans %= mod;
    }
    k *= k;
    if (mod) k %= mod;
    m >>= 1;
  }
  return ans;
}
template <class t1, class t2>
inline void add(t1& a, t2 b, int mod = -1) {
  if (mod == -1) mod = 1000000007;
  a += b;
  while (a >= mod) a -= mod;
  while (a < 0) a += mod;
}
template <class t>
void output1(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for (int i = 0; i < (int)arr.size(); i++) output1(arr[i]);
}
struct SegmentNode {
  int be, en;
  long long peak, sec_peak, sum, cnt_peak, cnt;
  long long lazy_add;
};
class SegmentTree {
 public:
  int l;
  long long inf;
  SegmentNode tree[150100 * 4];
  function<bool(const long long&, const long long&)> comp;
  inline int GetLeft(int no) { return no << 1; }
  inline int GetRight(int no) { return (no << 1) + 1; }
  inline int GetFa(int no) { return no >> 1; }
  SegmentTree(function<bool(const long long&, const long long&)> func) {
    l = 0;
    comp = func;
    if (comp(std::numeric_limits<long long>::min(),
             std::numeric_limits<long long>::max())) {
      inf = std::numeric_limits<long long>::max();
    } else {
      inf = std::numeric_limits<long long>::min();
    }
  }
  void Build(int no, int l, int r) {
    if (l > r) r = l;
    if (l == r) {
      tree[no].be = tree[no].en = l;
      tree[no].lazy_add = 0;
      tree[no].sum = tree[no].cnt = 0;
      tree[no].peak = tree[no].sec_peak = inf;
      tree[no].cnt_peak = 0;
      return;
    }
    tree[no].be = l;
    tree[no].en = r;
    int mid = (l + r) / 2;
    Build(GetLeft(no), l, mid);
    Build(GetRight(no), mid + 1, r);
    tree[no].lazy_add = 0;
    PushUp(no);
  }
  inline void PushUp(int no) {
    int le = GetLeft(no), ri = GetRight(no);
    tree[no].sum = tree[le].sum + tree[ri].sum;
    tree[no].cnt = tree[le].cnt + tree[ri].cnt;
    if (comp(tree[le].peak, tree[ri].peak)) {
      tree[no].peak = tree[le].peak;
      tree[no].cnt_peak = tree[le].cnt_peak;
      tree[no].sec_peak = comp(tree[le].sec_peak, tree[ri].peak)
                              ? tree[le].sec_peak
                              : tree[ri].peak;
    } else if (comp(tree[ri].peak, tree[le].peak)) {
      tree[no].peak = tree[ri].peak;
      tree[no].cnt_peak = tree[ri].cnt_peak;
      tree[no].sec_peak = comp(tree[ri].sec_peak, tree[le].peak)
                              ? tree[ri].sec_peak
                              : tree[le].peak;
    } else {
      tree[no].peak = tree[le].peak;
      tree[no].cnt_peak = tree[le].cnt_peak + tree[ri].cnt_peak;
      tree[no].sec_peak = comp(tree[ri].sec_peak, tree[le].sec_peak)
                              ? tree[ri].sec_peak
                              : tree[le].sec_peak;
    }
    tree[no].lazy_add = 0;
  }
  inline void PushDown(int no) {
    int le = GetLeft(no), ri = GetRight(no);
    if (tree[no].lazy_add) {
      tree[le].lazy_add += tree[no].lazy_add;
      tree[le].sum += tree[no].lazy_add * tree[le].cnt;
      if (tree[le].peak != inf) tree[le].peak += tree[no].lazy_add;
      if (tree[le].sec_peak != inf) tree[le].sec_peak += tree[no].lazy_add;
      tree[ri].lazy_add += tree[no].lazy_add;
      tree[ri].sum += tree[no].lazy_add * tree[ri].cnt;
      if (tree[ri].peak != inf) tree[ri].peak += tree[no].lazy_add;
      if (tree[ri].sec_peak != inf) tree[ri].sec_peak += tree[no].lazy_add;
    }
    if (comp(tree[le].peak, tree[no].peak)) {
      tree[le].sum -= tree[le].cnt_peak * (tree[le].peak - tree[no].peak);
      tree[le].peak = tree[no].peak;
    }
    if (comp(tree[ri].peak, tree[no].peak)) {
      tree[ri].sum -= tree[ri].cnt_peak * (tree[ri].peak - tree[no].peak);
      tree[ri].peak = tree[no].peak;
    }
    tree[no].lazy_add = 0;
  }
  void UpdTo(int l, int r, int no, long long bound) {
    if (l > r) return;
    if (l <= tree[no].be && r >= tree[no].en &&
        !comp(tree[no].sec_peak, bound)) {
      if (comp(tree[no].peak, bound)) {
        tree[no].sum -= tree[no].cnt_peak * (tree[no].peak - bound);
        tree[no].peak = bound;
      }
      return;
    }
    if (tree[no].be != tree[no].en) PushDown(no);
    int mid = (tree[no].be + tree[no].en) >> 1;
    if (r >= tree[no].be && l <= mid) UpdTo(l, r, GetLeft(no), bound);
    if (r >= mid + 1 && l <= tree[no].en) UpdTo(l, r, GetRight(no), bound);
    PushUp(no);
  }
  void UpdAdd(int l, int r, int no, long long ranadd) {
    if (l > r) return;
    if (l <= tree[no].be && r >= tree[no].en) {
      tree[no].lazy_add += ranadd;
      tree[no].sum += ranadd * tree[no].cnt;
      if (comp(tree[no].peak, inf)) tree[no].peak += ranadd;
      if (comp(tree[no].sec_peak, inf)) tree[no].sec_peak += ranadd;
      return;
    }
    if (tree[no].be != tree[no].en) PushDown(no);
    int mid = (tree[no].be + tree[no].en) >> 1;
    if (r >= tree[no].be && l <= mid) UpdAdd(l, r, GetLeft(no), ranadd);
    if (r >= mid + 1 && l <= tree[no].en) UpdAdd(l, r, GetRight(no), ranadd);
    PushUp(no);
  }
  void AddNewVal(int loc, int no, long long new_val) {
    if (loc <= tree[no].be && loc >= tree[no].en) {
      tree[no].cnt = 1;
      tree[no].sum = new_val;
      tree[no].peak = new_val;
      tree[no].cnt_peak = 1;
      tree[no].lazy_add = 0;
      return;
    }
    if (tree[no].be != tree[no].en) PushDown(no);
    int mid = (tree[no].be + tree[no].en) >> 1;
    if (loc <= mid)
      AddNewVal(loc, GetLeft(no), new_val);
    else
      AddNewVal(loc, GetRight(no), new_val);
    PushUp(no);
  }
  long long GetSum(int l, int r, int no) {
    if (l > r) return 0;
    if (l <= tree[no].be && r >= tree[no].en) return tree[no].sum;
    if (tree[no].be != tree[no].en) PushDown(no);
    long long ans = 0;
    int mid = (tree[no].be + tree[no].en) >> 1;
    if (r >= tree[no].be && l <= mid) ans += GetSum(l, r, GetLeft(no));
    if (r >= mid + 1 && l <= tree[no].en) ans += GetSum(l, r, GetRight(no));
    return ans;
  }
  int GetRank(int rank, int no) {
    if (rank > tree[no].sum) return -1;
    if (tree[no].be == tree[no].en) return tree[no].be;
    if (tree[no].be != tree[no].en) PushDown(no);
    if (rank <= tree[GetLeft(no)].sum) return GetRank(rank, GetLeft(no));
    return GetRank(rank - tree[GetLeft(no)].sum, GetRight(no));
  }
  inline int GetSectionRank(int l, int r, int rank) {
    return GetRank(rank + GetSum(0, l - 1, 1), 1);
  }
};
SegmentTree sgt_big([](const long long& a, const long long& b) {
  return a > b;
});
SegmentTree sgt_small([](const long long& a, const long long& b) {
  return a < b;
});
const int maxn = 150100;
int n;
int orig[maxn], loc[maxn], rk[maxn];
template <class t>
struct tree_array {
  t num[1 << 18], n, bigwei;
  void init(int nn = 1 << 18) {
    n = nn;
    while (lowb(nn) != nn) nn -= lowb(nn);
    bigwei = nn;
    n = bigwei * 2;
  }
  void upd(int no, t add) {
    while (no <= n) {
      num[no] += add;
      no += lowb(no);
    }
  }
  t que(int no) {
    t ans = 0;
    while (no) {
      ans += num[no];
      no -= lowb(no);
    }
    return ans;
  }
  int getrank(t x) {
    int ans = 0, ranwei = bigwei;
    t rank = 0;
    while (ranwei) {
      if (rank + num[ranwei + ans] < x) {
        ans += ranwei;
        rank += num[ans];
      }
      ranwei >>= 1;
    }
    return ans + 1;
  }
};
tree_array<int> ta;
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d", &n);
  ta.init(n + 10);
  for (int i = 0; i < n; i++) {
    scanf("%d", orig + i);
    loc[orig[i]] = i;
    rk[orig[i]] = ta.que(orig[i]) + 1;
    ta.upd(orig[i], 1);
  }
  sgt_big.Build(1, 0, n - 1);
  sgt_small.Build(1, 0, n - 1);
  for (int i = 1; i <= n; i++) {
    sgt_big.AddNewVal(loc[i], 1, i);
    sgt_small.AddNewVal(loc[i], 1, 0);
    sgt_big.UpdAdd(loc[i] + 1, n - 1, 1, 1);
    sgt_small.UpdAdd(loc[i] + 1, n - 1, 1, 1);
    sgt_big.UpdTo(0, loc[i] - 1, 1, rk[i] - 1);
    sgt_small.UpdTo(loc[i] + 1, n - 1, 1, rk[i]);
    printf("%I64d\n",
           sgt_big.GetSum(0, n - 1, 1) - sgt_small.GetSum(0, n - 1, 1));
  }
  return 0;
}
