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>
namespace mem {
namespace stdval {
using i32 = int;
using i64 = long long int;
using u32 = unsigned int;
using u64 = unsigned long long int;
using f32 = float;
using f64 = double;
using f96 = long double;
using i128 = __int128_t;
using u128 = __uint128_t;
}  // namespace stdval
namespace utils {
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::function;
using std::lower_bound;
using std::make_pair;
using std::make_tuple;
using std::max_element;
using std::min_element;
using std::reverse;
using std::shuffle;
using std::sort;
using std::swap;
using std::tie;
using std::unique;
using std::upper_bound;
}  // namespace utils
namespace random {
const int LuckyNumber = 20040726;
std::mt19937 rng(LuckyNumber ^
                 std::chrono::steady_clock::now().time_since_epoch().count());
std::mt19937_64 rng64(
    LuckyNumber ^ std::chrono::steady_clock::now().time_since_epoch().count());
template <class T>
inline T rand(T l, T r) {
  return std::uniform_int_distribution<T>(l, r)(rng);
}
template <class T>
inline T rand64(T l, T r) {
  return std::uniform_int_distribution<T>(l, r)(rng);
}
}  // namespace random
namespace modint {
template <const int mod>
struct Z {
  int x;
  inline Z() { x = 0; }
  inline Z(int t) { x = t; }
  inline void operator-=(Z a) { (x -= a.x) < 0 && (x += mod); }
  inline void operator+=(Z a) { (x += a.x) >= mod && (x -= mod); }
  inline void operator*=(Z a) { x = (long long)x * a.x % mod; }
  friend inline Z operator*(Z a, Z b) { return (long long)a.x * b.x % mod; }
  friend inline Z operator-(Z a, Z b) {
    return ((a.x -= b.x) < 0 && (a.x += mod)), a;
  }
  friend inline Z operator+(Z a, Z b) {
    return ((a.x += b.x) >= mod && (a.x -= mod)), a;
  }
};
template <const int mod>
inline Z<mod> finv(Z<mod> x) {
  if (x.x < 2) return x;
  return (mod - mod / x.x) * finv(mod % x.x);
}
template <const int mod>
inline Z<mod> fpow(Z<mod> a, int b) {
  Z<mod> s = 1;
  for (; b; b >>= 1, a = a * a)
    if (b & 1) s = s * a;
  return s;
}
template <const int mod>
inline void init_inverse(int n, Z<mod> *inv) {
  inv[0] = inv[1] = 1;
  for (int i = 2; i < n; i++) inv[i] = (mod - mod / i) * inv[mod % i];
}
template <const int mod>
inline void init_factorial(int n, Z<mod> *fac, Z<mod> *ifac) {
  fac[0] = 1, init_inverse(n, ifac);
  for (int i = 1; i < n; i++)
    fac[i] = fac[i - 1] * i, ifac[i] = ifac[i - 1] * ifac[i];
}
}  // namespace modint
namespace io {
template <const int mod>
inline void read(modint::Z<mod> &x) {
  read(x.x);
}
template <const int mod>
inline void print(modint::Z<mod> x) {
  print(x.x);
}
}  // namespace io
namespace math {
using std::max;
using std::min;
template <class T>
inline T abs(T x) {
  return x < 0 ? -x : x;
}
template <class T>
inline T gcd(T n, T m) {
  return m ? gcd(m, n % m) : n;
}
template <class T>
inline T lcm(T n, T m) {
  return n / gcd(n, m) * m;
}
template <const stdval::u64 p>
struct FastDiv {
  stdval::u64 t, i;
  inline FastDiv() : t(stdval::u64(-1) / p), i(mul_inv(p)) {}
  inline bool divide(stdval::u64 n) { return n * i <= t; }
  inline bool divide(stdval::i64 n) {
    return stdval::u64(n < 0 ? -n : n) * i <= t;
  }
  inline stdval::u64 mul_inv(stdval::u64 n) {
    stdval::u64 x = n;
    for (int i = 0; i < 5; ++i) x *= 2 - n * x;
    return x;
  }
};
template <const stdval::u64 b>
struct FastMod {
  stdval::u64 m;
  inline FastMod() : m(stdval::u64((stdval::u128(1) << 64) / b)) {}
  inline stdval::u64 reduce(stdval::u64 a) {
    stdval::u64 q = (stdval::u64)((stdval::u128(m) * a) >> 64);
    stdval::u64 r = a - q * b;
    return r >= b ? r - b : r;
  }
};
}  // namespace math
namespace container {
using std::make_pair;
using std::make_tuple;
using std::map;
using std::pair;
using std::set;
using std::tie;
using std::tuple;
using std::unordered_map;
using std::unordered_set;
template <class T>
struct vector : std::vector<T> {
  using std::vector<T>::vector;
  vector() : std::vector<T>() {}
  vector(const std::vector<T> &plain) : std::vector<T>(plain) {}
  inline void sort() { std::sort(this->begin(), this->end()); }
  inline void concat(const vector &rhs) {
    this->insert(this->end(), rhs.begin(), rhs.end());
  }
  inline bool includes(const T &x) const {
    return std::find(this->begin(), this->end(), x) != this->end();
  }
  template <class Function>
  inline void forEach(Function func) {
    for (const auto &it : *this) func(it);
  }
  inline vector slice(int l, int r) const {
    if (l > r) return {};
    if (r < this->size()) return vector(this->begin() + l, this->begin() + r);
    vector<int> rsp = (this->begin() + l, this->end());
    return rsp.resize(r - l), rsp;
  }
  inline void from(const std::set<T> &src) {
    this->resize(src.size());
    auto it = this->begin();
    for (const T e : src) *it++ = e;
  }
  template <class R, class Function>
  inline vector<R> _map(Function func) const {
    vector<R> res(this->size());
    for (size_t i = 0; i < this->size(); i++)
      res[i] = func(this->operator[](i));
    return res;
  }
  template <class R>
  inline vector<R> map(R func(T)) const {
    return this->_map<R>(func);
  }
  template <class R>
  inline vector<R> map(const std::function<R(T)> &func) const {
    return this->_map<R>(func);
  }
};
struct string : std::string {
  using std::string::string;
  string() : std::string("") {}
  string(const std::string &plain) : std::string(plain) {}
  template <class T>
  inline string join(const vector<T> &vet) const;
  vector<string> split(const string &dim) const {
    if (this->empty()) return {};
    char *src = new char[this->length() + 1];
    strcpy(src, this->c_str());
    char *tar = new char[dim.length() + 1];
    strcpy(tar, dim.c_str());
    vector<string> rsp;
    for (char *pos = strtok(src, tar); pos; pos = strtok(nullptr, tar))
      rsp.push_back(string(pos));
    delete[] src;
    delete[] tar;
    return rsp;
  }
  template <class... Args>
  static inline string format(const char *fm, Args... args) {
    int len = snprintf(nullptr, 0, fm, args...);
    char *buf = new char[len + 1];
    snprintf(buf, len + 1, fm, args...);
    string str(buf);
    delete[] buf;
    return str;
  }
  template <class... Args>
  static inline string format(const string &fm, Args... args) {
    return format(fm.c_str(), args...);
  }
};
inline string to_string(const float &x) { return std::to_string(x); }
inline string to_string(const double &x) { return std::to_string(x); }
inline string to_string(const long double &x) { return std::to_string(x); }
inline string to_string(const int &x) { return std::to_string(x); }
inline string to_string(const unsigned int &x) { return std::to_string(x); }
inline string to_string(const long long int &x) { return std::to_string(x); }
inline string to_string(const unsigned long long int &x) {
  return std::to_string(x);
}
inline string to_string(const string &s) { return s; }
inline string to_string(const char *s) { return string(s); }
inline string to_string(const std::string &s) { return string(s); }
template <const int mod>
inline string to_string(const mem::modint::Z<mod> &v) {
  return std::to_string(v.x);
}
template <class T>
inline string to_string(const vector<T> &ctn) {
  return "[" + string(",").join(ctn) + "]";
}
template <class T>
inline string to_string(const set<T> &ctn) {
  string result = "{";
  bool flag = false;
  for (const auto &it : ctn) {
    if (flag) result += ",";
    flag = true;
    result += to_string(it);
  }
  return result + "}";
}
template <class T1, class T2>
inline string to_string(const map<T1, T2> &ctn) {
  string result = "{";
  bool flag = false;
  for (const auto &it : ctn) {
    if (flag) result += ",";
    flag = true;
    result += to_string(it.first) + ":" + to_string(it.second);
  }
  return result + "}";
}
template <class T>
inline string string::join(const vector<T> &vet) const {
  if (!vet.size()) return "";
  string res = to_string(vet[0]);
  for (size_t i = 1; i < vet.size(); i++) {
    res += *this;
    res += to_string(vet[i]);
  }
  return res;
}
inline string operator"" _s(const char *s) { return string(s); }
inline string operator"" _s(const char *s, size_t len) {
  return string(s, len);
}
inline string operator"" _s(long double x) { return to_string(x); }
inline string operator"" _s(unsigned long long int x) { return to_string(x); }
}  // namespace container
namespace io {
namespace fastio {
const int BUFFER = 1 << 18;
char ibuf[BUFFER], *iS, *iT;
inline int getc() {
  if (iS == iT) {
    iT = (iS = ibuf) + fread(ibuf, 1, BUFFER, stdin);
    return iS == iT ? EOF : *iS++;
  } else {
    return *iS++;
  }
}
char obuf[BUFFER], *oS = obuf, *oT = oS + BUFFER - 1;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(int x) {
  *oS++ = x;
  if (oS == oT) flush();
}
struct Flusher {
  ~Flusher() { flush(); }
} flusher;
}  // namespace fastio
using fastio::getc;
using fastio::putc;
template <class T>
inline void readDigit(T &x) {
  x = getc();
  while (!isdigit(x)) x = getc();
}
inline int readDigit() {
  int x;
  readDigit(x);
  return x;
}
template <class T>
inline void readAlpha(T &x) {
  x = getc();
  while (!isalpha(x)) x = getc();
}
inline int readAlpha() {
  int x;
  readAlpha(x);
  return x;
}
inline void read(int &x) {
  x = 0;
  bool f = 0;
  char c = getc();
  while (!isdigit(c)) f ^= c == '-', c = getc();
  while (isdigit(c)) x = x * 10 + c - '0', c = getc();
  if (f) x = -x;
}
inline void read(unsigned int &x) {
  x = 0;
  bool f = 0;
  char c = getc();
  while (!isdigit(c)) f ^= c == '-', c = getc();
  while (isdigit(c)) x = x * 10 + c - '0', c = getc();
  if (f) x = -x;
}
inline void read(long long int &x) {
  x = 0;
  bool f = 0;
  char c = getc();
  while (!isdigit(c)) f ^= c == '-', c = getc();
  while (isdigit(c)) x = x * 10 + c - '0', c = getc();
  if (f) x = -x;
}
inline void read(unsigned long long int &x) {
  x = 0;
  bool f = 0;
  char c = getc();
  while (!isdigit(c)) f ^= c == '-', c = getc();
  while (isdigit(c)) x = x * 10 + c - '0', c = getc();
  if (f) x = -x;
}
inline void read(char &x) { x = getc(); }
inline void read(char *s) {
  char c = getc();
  while (~c && !isspace(c)) *s++ = c, c = getc();
  *s++ = '\0';
}
inline void read(container::string &s) {
  char c = getc();
  s = "";
  while (~c && !isspace(c)) s += c, c = getc();
}
template <class T = int>
inline T read() {
  T x;
  read(x);
  return x;
}
template <class T, class... Args>
inline void read(T &x, Args &...args) {
  read(x), read(args...);
}
inline void print(int x) {
  if (x < 0) putc('-'), x = -x;
  if (x > 9) print(x / 10);
  putc('0' + x % 10);
}
inline void print(unsigned int x) {
  if (x < 0) putc('-'), x = -x;
  if (x > 9) print(x / 10);
  putc('0' + x % 10);
}
inline void print(long long int x) {
  if (x < 0) putc('-'), x = -x;
  if (x > 9) print(x / 10);
  putc('0' + x % 10);
}
inline void print(unsigned long long int x) {
  if (x < 0) putc('-'), x = -x;
  if (x > 9) print(x / 10);
  putc('0' + x % 10);
}
inline void print(char x) { putc(x); }
inline void print(const char *s) {
  int len = strlen(s);
  for (int i = 0; i < len; i++) putc(s[i]);
}
inline void print(const container::string &s) {
  for (int i = 0; i < s.length(); i++) putc(s[i]);
}
template <class T, class... Args>
inline void print(const T &x, Args... args) {
  print(x), print(args...);
}
template <class... Args>
inline void println(Args... args) {
  print(args...), putc('\n');
}
template <class... Args>
inline void printfm(const char *formatter, Args... arguments) {
  print(container::string().format(formatter, arguments...));
}
template <class... Args>
inline void printfm(const container::string &formatter, Args... arguments) {
  print(container::string().format(formatter, arguments...));
}
}  // namespace io
namespace logger {
enum ConsoleColor {
  NOPE = -1,
  BLACK,
  RED,
  GREEN,
  YELLOW,
  BLUE,
  PURPLE,
  DEEPBLUE
};
template <const ConsoleColor color = NOPE, class... Args>
inline void log(const char *formatter, Args... args) {
  if (~color) {
    fprintf(stderr, "\033[%dm", 30 + color);
    fprintf(stderr, formatter, args...);
    fprintf(stderr, "\033[0m");
  } else {
    fprintf(stderr, formatter, args...);
  }
}
template <const ConsoleColor color = NOPE, class... Args>
inline void logln(const char *formatter, Args... args) {
  if (~color) {
    fprintf(stderr, "\033[%dm", 30 + color);
    fprintf(stderr, formatter, args...);
    fprintf(stderr, "\033[0m\n");
  } else {
    fprintf(stderr, formatter, args...);
    fprintf(stderr, "\n");
  }
}
template <class T>
inline void logs(const T &x) {
  fprintf(stderr, container::to_string(x).c_str());
}
template <class T, class... Args>
inline void logs(const T &x, Args... args) {
  logs(x), logs(args...);
}
template <class... Args>
inline void logsln(Args... args) {
  logs(args...);
  fprintf(stderr, "\n");
}
}  // namespace logger
using namespace io;
using namespace math;
using namespace utils;
using namespace modint;
using namespace random;
using namespace stdval;
using namespace logger;
using namespace container;
}  // namespace mem
const int N = 1.5e5 + 10;
using namespace mem::io;
using namespace mem::logger;
int n, a[N], p[N];
struct SegmentTree {
  struct segment {
    int l, r, mid, cnt, tag;
    long long sum;
  } p[N << 2];
  inline void maintain(int u) {
    p[u].cnt = p[u << 1].cnt + p[u << 1 | 1].cnt;
    p[u].sum =
        p[u << 1].sum + p[u << 1 | 1].sum + (long long)p[u].cnt * p[u].tag;
  }
  void build(int u, int l, int r) {
    p[u].l = l, p[u].r = r, p[u].mid = (l + r) >> 1;
    if (l == r) return;
    build(u << 1, l, p[u].mid);
    build(u << 1 | 1, p[u].mid + 1, r);
  }
  void modify(int u, int l, int r, int x) {
    if (p[u].l == l && p[u].r == r) {
      p[u].tag += x;
      p[u].sum += (long long)x * p[u].cnt;
      return;
    }
    if (r <= p[u].mid)
      modify(u << 1, l, r, x);
    else if (l > p[u].mid)
      modify(u << 1 | 1, l, r, x);
    else {
      modify(u << 1, l, p[u].mid, x);
      modify(u << 1 | 1, p[u].mid + 1, r, x);
    }
    maintain(u);
  }
  void update(int u, int k) {
    if (p[u].l == p[u].r) {
      p[u].cnt++;
      p[u].sum += p[u].tag;
      return;
    }
    update(k <= p[u].mid ? u << 1 : u << 1 | 1, k);
    maintain(u);
  }
  inline long long query(int k, int x) { return p[1].sum; }
} V;
struct JirySegmentTree {
  struct segment {
    int l, r, mid, max, smx, cnt;
  } p[N << 2];
  std::function<int(int)> init;
  std::function<void(int, int)> upd;
  inline void pushdown(int u) {
    p[u << 1].max = std::min(p[u].max, p[u << 1].max);
    p[u << 1 | 1].max = std::min(p[u].max, p[u << 1 | 1].max);
  }
  inline void maintain(int u) {
    if (p[u << 1].max > p[u << 1 | 1].max) {
      p[u].max = p[u << 1].max;
      p[u].cnt = p[u << 1].cnt;
      p[u].smx = std::max(p[u << 1].smx, p[u << 1 | 1].max);
    } else if (p[u << 1 | 1].max > p[u << 1].max) {
      p[u].max = p[u << 1 | 1].max;
      p[u].cnt = p[u << 1 | 1].cnt;
      p[u].smx = std::max(p[u << 1 | 1].smx, p[u << 1].max);
    } else {
      p[u].max = p[u << 1].max;
      p[u].cnt = p[u << 1].cnt + p[u << 1 | 1].cnt;
      p[u].smx = std::max(p[u << 1].smx, p[u << 1 | 1].smx);
    }
  }
  inline void set(int u, int x) {
    upd(p[u].max, -1);
    p[u].max = x;
    upd(p[u].max, 1);
  }
  void build(int u, int l, int r) {
    p[u].l = l, p[u].r = r, p[u].mid = (l + r) >> 1;
    if (l == r) {
      p[u].cnt = 1, p[u].max = init(l), p[u].smx = -1;
      upd(p[u].max, 1);
      return;
    }
    build(u << 1, l, p[u].mid);
    build(u << 1 | 1, p[u].mid + 1, r);
    maintain(u);
  }
  void modify(int u, int k, int x) {
    if (p[u].l == p[u].r) return set(u, x);
    pushdown(u);
    modify(k <= p[u].mid ? u << 1 : u << 1 | 1, k, x);
    maintain(u);
  }
  void update(int u, int l, int r, int x) {
    if (p[u].max <= x) return;
    if (p[u].l == p[u].r) {
      set(u, x);
      return;
    }
    if (p[u].l == l && p[u].r == r && p[u].smx < x) {
      upd(p[u].max, -p[u].cnt);
      p[u].max = x;
      upd(p[u].max, p[u].cnt);
      return;
    }
    pushdown(u);
    if (r <= p[u].mid)
      update(u << 1, l, r, x);
    else if (l > p[u].mid)
      update(u << 1 | 1, l, r, x);
    else {
      update(u << 1, l, p[u].mid, x);
      update(u << 1 | 1, p[u].mid + 1, r, x);
    }
    maintain(u);
  }
  int query(int u, int k) {
    if (p[u].l == p[u].r) return p[u].max;
    pushdown(u);
    int res = query(k <= p[u].mid ? u << 1 : u << 1 | 1, k);
    maintain(u);
    return res;
  }
} L, R;
int main() {
  read(n);
  V.build(1, 1, n);
  L.upd = [&](int k, int x) {
    if (k) V.modify(1, 1, -k, -x);
  };
  L.init = [&](int k) { return -n; };
  L.build(1, 1, n);
  R.upd = [&](int k, int x) {
    if (k - 1) V.modify(1, 1, k - 1, x);
  };
  R.init = [&](int k) { return 1; };
  R.build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    read(a[i]);
    p[a[i]] = i;
  }
  for (int i = 1; i <= n; i++) {
    V.update(1, p[i]);
    if (1 < p[i]) R.update(1, 1, p[i] - 1, p[i]);
    if (p[i] < n) L.update(1, p[i] + 1, n, -p[i]);
    L.modify(1, p[i], 0);
    R.modify(1, p[i], n + 1);
    print(V.p[1].sum + (long long)V.p[1].cnt * (n - i), '\n');
  }
}
