#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &x) {
  int f = 0;
  x = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  if (f) x = -x;
}
const int N = 300005;
struct seg {
  int mx[N << 2], T[N << 2], c[N << 2];
  int calc(int o, int l, int r, int val) {
    if (l == r) return mx[o] > val;
    if (val < mx[(o << 1)])
      return T[o] + calc((o << 1), l, ((l + r) >> 1), val);
    return calc((o << 1 | 1), ((l + r) >> 1) + 1, r, val);
  }
  void upd(int o, int l, int r, int x, int val) {
    if (l == r) {
      mx[o] = val, c[o]++;
      return;
    }
    if (x <= ((l + r) >> 1))
      upd((o << 1), l, ((l + r) >> 1), x, val);
    else
      upd((o << 1 | 1), ((l + r) >> 1) + 1, r, x, val);
    mx[o] = max(mx[(o << 1)], mx[(o << 1 | 1)]);
    T[o] = calc((o << 1 | 1), ((l + r) >> 1) + 1, r, mx[(o << 1)]);
    c[o] = c[(o << 1)] + c[(o << 1 | 1)];
  }
  int qry(int o, int l, int r, int x, int y, int &ret) {
    if (x > y || r < x || y < l) return 0;
    if (l == x && y == r) {
      int res = calc(o, l, r, ret);
      return ret = max(ret, mx[o]), res;
    }
    if (y <= ((l + r) >> 1)) return qry((o << 1), l, ((l + r) >> 1), x, y, ret);
    if (((l + r) >> 1) < x)
      return qry((o << 1 | 1), ((l + r) >> 1) + 1, r, x, y, ret);
    int res = qry((o << 1), l, ((l + r) >> 1), x, ((l + r) >> 1), ret);
    return res +
           qry((o << 1 | 1), ((l + r) >> 1) + 1, r, ((l + r) >> 1) + 1, y, ret);
  }
  int count(int o, int l, int r, int x, int y) {
    if (x > y || r < x || y < l) return 0;
    if (l == x && y == r) return c[o];
    if (y <= ((l + r) >> 1)) return count((o << 1), l, ((l + r) >> 1), x, y);
    if (((l + r) >> 1) < x)
      return count((o << 1 | 1), ((l + r) >> 1) + 1, r, x, y);
    int res = count((o << 1), l, ((l + r) >> 1), x, ((l + r) >> 1));
    return res +
           count((o << 1 | 1), ((l + r) >> 1) + 1, r, ((l + r) >> 1) + 1, y);
  }
  int Find(int o, int l, int r, int x, int val) {
    if (x > r) return 0;
    if (x <= l && mx[o] < val) return 0;
    if (l == r) return l;
    int ret =
        (x <= ((l + r) >> 1) ? Find((o << 1), l, ((l + r) >> 1), x, val) : 0);
    return ret ? ret : Find((o << 1 | 1), ((l + r) >> 1) + 1, r, x, val);
  }
} L, R;
int a[N], p[N], n;
vector<int> pre, suf;
long long ans;
int main() {
  read(n);
  for (int i = (1); i <= (n); i++) {
    read(a[i]);
    p[a[i]] = i;
  }
  for (int i = (1); i <= (n); i++) {
    int l = p[i], r = p[i], flag = -1;
    pre.clear();
    suf.clear();
    for (;;) {
      int vl = (l == p[i] ? 1 : a[l]);
      int vr = (r == p[i] ? 1 : a[r]);
      l = n + 1 - L.Find(1, 1, n, n + 1 - l + 1, vl);
      r = R.Find(1, 1, n, r + 1, vr);
      if (!r) {
        flag = 1;
        break;
      }
      if (l == n + 1) {
        flag = 0;
        break;
      }
      pre.push_back(l), suf.push_back(r);
    }
    if (flag) {
      suf.push_back(n + 1);
      int sz = suf.size() - 1;
      for (int j = 0; j < (sz); j++) {
        int cr = R.count(1, 1, n, suf[j], suf[j + 1] - 1);
        int pos = n + 1 - L.Find(1, 1, n, n + 1 - p[i], a[suf[j]]);
        if (pos == n + 1) {
          ans -= R.count(1, 1, n, 1, p[i]);
          continue;
        }
        ans -= R.count(1, 1, n, pos + 1, p[i]);
        int tmp = a[suf[j]];
        ans -= (long long)cr * L.qry(1, 1, n, n + 1 - pos, n, tmp);
      }
    } else {
      pre.push_back(0);
      int sz = pre.size() - 1;
      for (int j = 0; j < (sz); j++) {
        int cl = R.count(1, 1, n, pre[j + 1] + 1, pre[j]);
        int pos = R.Find(1, 1, n, p[i], a[pre[j]]);
        if (pos == 0) {
          ans -= R.count(1, 1, n, p[i], n);
          continue;
        }
        ans -= R.count(1, 1, n, p[i], pos - 1);
        int tmp = a[pre[j]];
        ans -= (long long)cl * R.qry(1, 1, n, pos, n, tmp);
      }
    }
    L.upd(1, 1, n, n + 1 - p[i], i);
    R.upd(1, 1, n, p[i], i);
    printf("%lld\n", ans += i);
  }
  return 0;
}
