B - Minimum Cost Sort
Source: atcoder
Difficulty: 600

Problem Statement
You are given a permutation
P = (P_1, P_2, \ldots, P_N)
of
(1, 2, \ldots, N)
. Takahashi can repeatedly perform the following operation on
P
(possibly zero times):
Choose an integer
i
satisfying
1 \leq i \leq N-1
. Pay a cost of
i
, and swap
P_i
and
P_{i+1}
.
Find the minimum total cost required to sort
P
in ascending order.
Constraints
2 \leq N \leq 2 \times 10^5
(P_1, P_2, \ldots, P_N)
is a permutation of
(1, 2, \ldots, N)
.
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
P_1
P_2
\ldots
P_N
Output
Print the minimum total cost required to sort
P
in ascending order.
Sample Input 1
3
3 2 1
Sample Output 1
4
Takahashi can sort
P
in ascending order as follows:
Pay a cost of
1
and swap
P_1 = 3
and
P_2 = 2
. Now,
P = (2, 3, 1)
.
Pay a cost of
2
and swap
P_2 = 3
and
P_3 = 1
. Now,
P = (2, 1, 3)
.
Pay a cost of
1
and swap
P_1 = 2
and
P_2 = 1
. Now,
P = (1, 2, 3)
.
The total cost for these operations is
4
, which is the minimum possible.
Sample Input 2
5
2 4 1 3 5
Sample Output 2
6
Sample Input 3
2
1 2
Sample Output 3
0

C++ solution:
#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,popcnt")
#endif
#include <bits/stdc++.h>
using namespace std;
using ll   =                long long;
using u32  =                unsigned int;
using u64  =                unsigned long long;
using i128 =                __int128;
using u128 =                __uint128_t;
using f128 =                __float128;
using ld   =                long double;
using pii  =                pair<int, int>;
using pll  =                pair<ll, ll>;
using vi   =                vector<int>;
using vvi  =                vector<vector<int>>;
using vll  =                vector<ll>;
using vvll =                vector<vector<ll>>;
using vpii =                vector<pii>;
using vpll =                vector<pll>;
template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'000'000'000;
template <>
constexpr ll infty<ll> = ll(infty<int>) * infty<int> * 2;
template <>
constexpr u32 infty<u32> = infty<int>;
template <>
constexpr u64 infty<u64> = infty<ll>;
template <>
constexpr i128 infty<i128> = i128(infty<ll>) * infty<ll>;
template <>
constexpr double infty<double> = infty<ll>;
template <>
constexpr long double infty<long double> = infty<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = std::priority_queue<T>;
template <class T>
using pqg = std::priority_queue<T, vector<T>, greater<T>>;
#define vv(type, name, h, ...) \
  vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...)   \
  vector<vector<vector<type>>> name( \
      h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...)       \
  vector<vector<vector<vector<type>>>> name( \
      a, vector<vector<vector<type>>>(       \
             b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
#define lb                  lower_bound
#define ub                  upper_bound
#define pb                  push_back
#define eb                  emplace_back
#define fi                  first
#define se                  second
#define mp                  make_pair
#define mt                  make_tuple
#define stoi                stoll
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload3(_1, _2, _3, name, ...) name
#define rep1(n)             for(ll _ = 0; _ < n; ++_)
#define rep2(i, n)          for(ll i = 0; i < n; ++i)
#define rep3(i, a, b)       for(ll i = a; i < b; ++i)
#define rep4(i, a, b, c)    for(int i = a; i < b; i += c)
#define rep(...)            overload4(__VA_ARGS__, rep4, rep3, rep2, rep1) (__VA_ARGS__)
#define rrep1(n)            for(ll i = n; i--; )
#define rrep2(i, n)         for(ll i = n; i--; )
#define rrep3(i, a, b)      for(ll i = a; i > b; i--)
#define rrep4(i, a, b, c)   for(ll i = a; i > b; i -= c)
#define rrep(...)           overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1) (__VA_ARGS__)
#define each1(i, a)         for(auto&& i : a)
#define each2(x, y, a)      for(auto&& [x, y] : a)
#define each3(x, y, z, a)   for(auto&& [x, y, z] : a)
#define each(...)           overload4(__VA_ARGS__, each3, each2, each1) (__VA_ARGS__)
#define FOR1(a)             for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a)          for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b)       for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c)    for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a)           for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a)        for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b)     for (ll i = (b)-1; i >= ll(a); --i)
#define FOR(...)            overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1) (__VA_ARGS__)
#define FOR_R(...)          overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R) (__VA_ARGS__)
#define FOR_subset(t, s)    for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define len(x)              ll(x.size())
#define elif                else if
#define all1(i)             begin(i), end(i)
#define all2(i, a)          begin(i), begin(i) + a
#define all3(i, a, b)       begin(i) + a, begin(i) + b
#define all(...)            overload3(__VA_ARGS__, all3, all2, all1) (__VA_ARGS__)
#define rall1(i)            rbegin(i), rend(i)
#define rall2(i, a)         rbegin(i), rbegin(i) + a
#define rall3(i, a, b)      rbegin(i) + a, rbegin(i) + b
#define rall(...)           overload3(__VA_ARGS__, rall3, rall2, rall1) (__VA_ARGS__)
#define MIN(v)              *min_element(all(v))
#define MAX(v)              *max_element(all(v))
#define LB(c, x)            distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x)            distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x)           sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()
#define SORT(a)             sort(all(a))
#define REV(a)              reverse(all(a))
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_mod_2(int x) { return __builtin_parity(x); }
int popcnt_mod_2(u32 x) { return __builtin_parity(x); }
int popcnt_mod_2(ll x) { return __builtin_parityll(x); }
int popcnt_mod_2(u64 x) { return __builtin_parityll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
template<class T> auto max(const T& a){ return *max_element(all(a)); }
template<class T> auto min(const T& a){ return *min_element(all(a)); }
template <typename T, typename U>
T ceil(T x, U y) {
    return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U>
T floor(T x, U y) {
    return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T, typename U>
T bmod(T x, U y) {
    return x - y * floor(x, y);
}
template <typename T, typename U>
pair<T, T> divmod(T x, U y) {
    T q = floor(x, y);
    return {q, x - q * y};
}
template <typename T, typename U>
T SUM(const vector<U> &A) {
    T sum = 0;
    for (auto &&a: A) sum += a;
    return sum;
}
template <typename T, typename U>
vector<T> cumsum(vector<U> &A, int off = 1) {
    int N = A.size();
    vector<T> B(N + 1);
    for (int i = 0; i < N; i++) B[i + 1] = B[i] + A[i];
    if (off == 0) B.erase(B.begin());
    return B;
}
template <typename T>
vector<int> argsort(const vector<T> &A) {
  vector<int> ids(len(A));
  iota(all(ids), 0);
  sort(all(ids),
       [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
  return ids;
}
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
  vc<T> B(len(I));
  FOR(i, len(I)) B[i] = A[I[i]];
  return B;
}
template <typename T, typename... Vectors>
void concat(vc<T> &first, const Vectors &... others) {
  vc<T> &res = first;
  (res.insert(res.end(), others.begin(), others.end()), ...);
}
template <typename T>
T POP(deque<T> &que) {
  T a = que.front();
  que.pop_front();
  return a;
}
template <typename T>
T POP(pq<T> &que) {
  T a = que.top();
  que.pop();
  return a;
}
template <typename T>
T POP(pqg<T> &que) {
  assert(!que.empty());
  T a = que.top();
  que.pop();
  return a;
}
template <typename T>
T POP(vc<T> &que) {
  assert(!que.empty());
  T a = que.back();
  que.pop_back();
  return a;
}
template <typename F>
ll binary_search(F check, ll ok, ll ng, bool check_ok = true) {
  if (check_ok) assert(check(ok));
  while (abs(ok - ng) > 1) {
    auto x = (ng + ok) / 2;
    (check(x) ? ok : ng) = x;
  }
  return ok;
}
template <typename F>
double binary_search_real(F check, double ok, double ng, int iter = 100) {
  while (iter--) {
    double x = (ok + ng) / 2;
    (check(x) ? ok : ng) = x;
  }
  return (ok + ng) / 2;
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
  return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
  return (a > b ? a = b, 1 : 0);
}
// ? は -1
vc<int> s_to_vi(const string &S, char first_char) {
  vc<int> A(S.size());
  FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); }
  return A;
}
#define FASTIO
#include <unistd.h>


// https://judge.yosupo.jp/submission/21623

namespace fastio {
static constexpr uint32_t SZ = 1 << 17;
char ibuf[SZ];
char obuf[SZ];
char out[100];
// pointer of ibuf, obuf

uint32_t pil = 0, pir = 0, por = 0;

struct Pre {
  char num[10000][4];
  constexpr Pre() : num() {
    for (int i = 0; i < 10000; i++) {
      int n = i;
      for (int j = 3; j >= 0; j--) {
        num[i][j] = n % 10 | '0';
        n /= 10;
      }
    }
  }
} constexpr pre;

inline void load() {
  memcpy(ibuf, ibuf + pil, pir - pil);
  pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin);
  pil = 0;
  if (pir < SZ) ibuf[pir++] = '\n';
}

inline void flush() {
  fwrite(obuf, 1, por, stdout);
  por = 0;
}

void rd(char &c) {
  do {
    if (pil + 1 > pir) load();
    c = ibuf[pil++];
  } while (isspace(c));
}

void rd(string &x) {
  x.clear();
  char c;
  do {
    if (pil + 1 > pir) load();
    c = ibuf[pil++];
  } while (isspace(c));
  do {
    x += c;
    if (pil == pir) load();
    c = ibuf[pil++];
  } while (!isspace(c));
}

template <typename T>
void rd_real(T &x) {
  string s;
  rd(s);
  x = stod(s);
}

template <typename T>
void rd_integer(T &x) {
  if (pil + 100 > pir) load();
  char c;
  do
    c = ibuf[pil++];
  while (c < '-');
  bool minus = 0;
  if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
    if (c == '-') { minus = 1, c = ibuf[pil++]; }
  }
  x = 0;
  while ('0' <= c) { x = x * 10 + (c & 15), c = ibuf[pil++]; }
  if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
    if (minus) x = -x;
  }
}

void rd(int &x) { rd_integer(x); }
void rd(ll &x) { rd_integer(x); }
void rd(i128 &x) { rd_integer(x); }
void rd(u32 &x) { rd_integer(x); }
void rd(u64 &x) { rd_integer(x); }
void rd(u128 &x) { rd_integer(x); }
void rd(double &x) { rd_real(x); }
void rd(long double &x) { rd_real(x); }
void rd(f128 &x) { rd_real(x); }

template <class T, class U>
void rd(pair<T, U> &p) {
  return rd(p.first), rd(p.second);
}
template <size_t N = 0, typename T>
void rd_tuple(T &t) {
  if constexpr (N < std::tuple_size<T>::value) {
    auto &x = std::get<N>(t);
    rd(x);
    rd_tuple<N + 1>(t);
  }
}
template <class... T>
void rd(tuple<T...> &tpl) {
  rd_tuple(tpl);
}

template <size_t N = 0, typename T>
void rd(array<T, N> &x) {
  for (auto &d: x) rd(d);
}
template <class T>
void rd(vc<T> &x) {
  for (auto &d: x) rd(d);
}

void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
  rd(h), read(t...);
}

void wt(const char c) {
  if (por == SZ) flush();
  obuf[por++] = c;
}
void wt(const string s) {
  for (char c: s) wt(c);
}
void wt(const char *s) {
  size_t len = strlen(s);
  for (size_t i = 0; i < len; i++) wt(s[i]);
}

template <typename T>
void wt_integer(T x) {
  if (por > SZ - 100) flush();
  if (x < 0) { obuf[por++] = '-', x = -x; }
  int outi;
  for (outi = 96; x >= 10000; outi -= 4) {
    memcpy(out + outi, pre.num[x % 10000], 4);
    x /= 10000;
  }
  if (x >= 1000) {
    memcpy(obuf + por, pre.num[x], 4);
    por += 4;
  } else if (x >= 100) {
    memcpy(obuf + por, pre.num[x] + 1, 3);
    por += 3;
  } else if (x >= 10) {
    int q = (x * 103) >> 10;
    obuf[por] = q | '0';
    obuf[por + 1] = (x - q * 10) | '0';
    por += 2;
  } else
    obuf[por++] = x | '0';
  memcpy(obuf + por, out + outi + 4, 96 - outi);
  por += 96 - outi;
}

template <typename T>
void wt_real(T x) {
  ostringstream oss;
  oss << fixed << setprecision(15) << double(x);
  string s = oss.str();
  wt(s);
}

void wt(int x) { wt_integer(x); }
void wt(ll x) { wt_integer(x); }
void wt(i128 x) { wt_integer(x); }
void wt(u32 x) { wt_integer(x); }
void wt(u64 x) { wt_integer(x); }
void wt(u128 x) { wt_integer(x); }
void wt(double x) { wt_real(x); }
void wt(long double x) { wt_real(x); }
void wt(f128 x) { wt_real(x); }

template <class T, class U>
void wt(const pair<T, U> val) {
  wt(val.first);
  wt(' ');
  wt(val.second);
}
template <size_t N = 0, typename T>
void wt_tuple(const T t) {
  if constexpr (N < std::tuple_size<T>::value) {
    if constexpr (N > 0) { wt(' '); }
    const auto x = std::get<N>(t);
    wt(x);
    wt_tuple<N + 1>(t);
  }
}
template <class... T>
void wt(tuple<T...> tpl) {
  wt_tuple(tpl);
}
template <class T, size_t S>
void wt(const array<T, S> val) {
  auto n = val.size();
  for (size_t i = 0; i < n; i++) {
    if (i) wt(' ');
    wt(val[i]);
  }
}
template <class T>
void wt(const vector<T> val) {
  auto n = val.size();
  for (size_t i = 0; i < n; i++) {
    if (i) wt(' ');
    wt(val[i]);
  }
}

void print() { wt('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
  wt(head);
  if (sizeof...(Tail)) wt(' ');
  print(forward<Tail>(tail)...);
}

// gcc expansion. called automaticall after main.

void __attribute__((destructor)) _d() { flush(); }
} // namespace fastio

using fastio::read;
using fastio::print;
using fastio::flush;

#ifndef ONLINE_JUDGE
#define SHOW(...) \
  SHOW_IMPL(__VA_ARGS__, SHOW4, SHOW3, SHOW2, SHOW1)(__VA_ARGS__)
#define SHOW_IMPL(_1, _2, _3, _4, NAME, ...) NAME
#define SHOW1(x) print(#x, "=", (x)), flush()
#define SHOW2(x, y) print(#x, "=", (x), #y, "=", (y)), flush()
#define SHOW3(x, y, z) print(#x, "=", (x), #y, "=", (y), #z, "=", (z)), flush()
#define SHOW4(x, y, z, w) \
  print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w)), flush()
#else
#define SHOW(...)
#endif

#define INT(...)   \
  int __VA_ARGS__; \
  read(__VA_ARGS__)
#define LL(...)   \
  ll __VA_ARGS__; \
  read(__VA_ARGS__)
#define U32(...)   \
  u32 __VA_ARGS__; \
  read(__VA_ARGS__)
#define U64(...)   \
  u64 __VA_ARGS__; \
  read(__VA_ARGS__)
#define STR(...)      \
  string __VA_ARGS__; \
  read(__VA_ARGS__)
#define CHAR(...)   \
  char __VA_ARGS__; \
  read(__VA_ARGS__)
#define DBL(...)      \
  double __VA_ARGS__; \
  read(__VA_ARGS__)

#define VEC(type, name, size) \
  vector<type> name(size);    \
  read(name)
#define VV(type, name, h, w)                     \
  vector<vector<type>> name(h, vector<type>(w)); \
  read(name)

void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }
template <typename Iterable>
auto print_all(const Iterable& v, std::string sep = " ", std::string end = "\n") -> decltype(fastio::wt(*v.begin())) {
    for (auto it = v.begin(); it != v.end();) {
        fastio::wt(*it);
        if (++it != v.end()) fastio::wt(sep);
    }
    fastio::wt(end);
}
vvi getGraph(int n, int m, bool directed = false) {
    vvi res(n);
    rep(_, 0, m) {
        INT(u, v);
        u--, v--;
        res[u].emplace_back(v);
        if(!directed) res[v].emplace_back(u);
    }
    return res;
}
vector<vpii> getWeightedGraph(int n, int m, bool directed = false) {
    vector<vpii> res(n);
    rep(_, 0, m) {
        INT(u, v, w);
        u--, v--;
        res[u].emplace_back(v, w);
        if(!directed) res[v].emplace_back(u, w);
    }
    return res;
}
template <class... Args> auto ndvector(size_t n, Args &&...args) {
    if constexpr (sizeof...(args) == 1) {
        return vector(n, args...);
    } else {
        return vector(n, ndvector(args...));
    }
}

#line 2 "alg/monoid/add.hpp"

template <typename E>
struct Monoid_Add {
  using X = E;
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
  static constexpr X inverse(const X &x) noexcept { return -x; }
  static constexpr X power(const X &x, ll n) noexcept { return X(n) * x; }
  static constexpr X unit() { return X(0); }
  static constexpr bool commute = true;
};
#line 3 "ds/fenwicktree/fenwicktree.hpp"

template <typename Monoid>
struct FenwickTree {
  using G = Monoid;
  using MX = Monoid;
  using E = typename G::value_type;
  int n;
  vector<E> dat;
  E total;

  FenwickTree() {}
  FenwickTree(int n) { build(n); }
  template <typename F>
  FenwickTree(int n, F f) {
    build(n, f);
  }
  FenwickTree(const vc<E>& v) { build(v); }

  void build(int m) {
    n = m;
    dat.assign(m, G::unit());
    total = G::unit();
  }
  void build(const vc<E>& v) {
    build(len(v), [&](int i) -> E { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m;
    dat.clear();
    dat.reserve(n);
    total = G::unit();
    FOR(i, n) { dat.eb(f(i)); }
    for (int i = 1; i <= n; ++i) {
      int j = i + (i & -i);
      if (j <= n) dat[j - 1] = G::op(dat[i - 1], dat[j - 1]);
    }
    total = prefix_sum(m);
  }

  E prod_all() { return total; }
  E sum_all() { return total; }
  E sum(int k) { return prefix_sum(k); }
  E prod(int k) { return prefix_prod(k); }
  E prefix_sum(int k) { return prefix_prod(k); }
  E prefix_prod(int k) {
    chmin(k, n);
    E ret = G::unit();
    for (; k > 0; k -= k & -k) ret = G::op(ret, dat[k - 1]);
    return ret;
  }
  E sum(int L, int R) { return prod(L, R); }
  E prod(int L, int R) {
    chmax(L, 0), chmin(R, n);
    if (L == 0) return prefix_prod(R);
    assert(0 <= L && L <= R && R <= n);
    E pos = G::unit(), neg = G::unit();
    while (L < R) { pos = G::op(pos, dat[R - 1]), R -= R & -R; }
    while (R < L) { neg = G::op(neg, dat[L - 1]), L -= L & -L; }
    return G::op(pos, G::inverse(neg));
  }

  vc<E> get_all() {
    vc<E> res(n);
    FOR(i, n) res[i] = prod(i, i + 1);
    return res;
  }

  void add(int k, E x) { multiply(k, x); }
  void multiply(int k, E x) {
    static_assert(G::commute);
    total = G::op(total, x);
    for (++k; k <= n; k += k & -k) dat[k - 1] = G::op(dat[k - 1], x);
  }
  void set(int k, E x) { add(k, G::op(G::inverse(prod(k, k + 1)), x)); }

  template <class F>
  int max_right(const F check, int L = 0) {
    assert(check(G::unit()));
    E s = G::unit();
    int i = L;
    // 2^k 進むとダメ
    int k = [&]() {
      while (1) {
        if (i % 2 == 1) { s = G::op(s, G::inverse(dat[i - 1])), i -= 1; }
        if (i == 0) { return topbit(n) + 1; }
        int k = lowbit(i) - 1;
        if (i + (1 << k) > n) return k;
        E t = G::op(s, dat[i + (1 << k) - 1]);
        if (!check(t)) { return k; }
        s = G::op(s, G::inverse(dat[i - 1])), i -= i & -i;
      }
    }();
    while (k) {
      --k;
      if (i + (1 << k) - 1 < len(dat)) {
        E t = G::op(s, dat[i + (1 << k) - 1]);
        if (check(t)) { i += (1 << k), s = t; }
      }
    }
    return i;
  }

  // check(i, x)
  template <class F>
  int max_right_with_index(const F check, int L = 0) {
    assert(check(L, G::unit()));
    E s = G::unit();
    int i = L;
    // 2^k 進むとダメ
    int k = [&]() {
      while (1) {
        if (i % 2 == 1) { s = G::op(s, G::inverse(dat[i - 1])), i -= 1; }
        if (i == 0) { return topbit(n) + 1; }
        int k = lowbit(i) - 1;
        if (i + (1 << k) > n) return k;
        E t = G::op(s, dat[i + (1 << k) - 1]);
        if (!check(i + (1 << k), t)) { return k; }
        s = G::op(s, G::inverse(dat[i - 1])), i -= i & -i;
      }
    }();
    while (k) {
      --k;
      if (i + (1 << k) - 1 < len(dat)) {
        E t = G::op(s, dat[i + (1 << k) - 1]);
        if (check(i + (1 << k), t)) { i += (1 << k), s = t; }
      }
    }
    return i;
  }

  template <class F>
  int min_left(const F check, int R) {
    assert(check(G::unit()));
    E s = G::unit();
    int i = R;
    // false になるところまで戻る
    int k = 0;
    while (i > 0 && check(s)) {
      s = G::op(s, dat[i - 1]);
      k = lowbit(i);
      i -= i & -i;
    }
    if (check(s)) {
      assert(i == 0);
      return 0;
    }
    // 2^k 進むと ok になる
    // false を維持して進む
    while (k) {
      --k;
      E t = G::op(s, G::inverse(dat[i + (1 << k) - 1]));
      if (!check(t)) { i += (1 << k), s = t; }
    }
    return i + 1;
  }

  int kth(E k, int L = 0) {
    return max_right([&k](E x) -> bool { return x <= k; }, L);
  }
};

void solve() {
    INT(n);
    VEC(int, P, n);
    each(i, P) i--;
    FenwickTree<Monoid_Add<ll>> fw(n);
    ll ans = 0;
    rep(i, n) {
        ll x = fw.sum(P[i], n);
        ans += x * (2 * i - x + 1) / 2;
        fw.add(P[i], 1);
    }
    print(ans);
}

signed main() {
    int T = 1;
    // read(T);
    while (T--) {
        solve();
    }
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

var iost *Iost

type Iost struct {
	Scanner *bufio.Scanner
	Writer  *bufio.Writer
}

func NewIost(fp io.Reader, wfp io.Writer) *Iost {
	const BufSize = 2000005
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, BufSize), BufSize)
	return &Iost{Scanner: scanner, Writer: bufio.NewWriter(wfp)}
}
func (i *Iost) Text() string {
	if !i.Scanner.Scan() {
		panic("scan failed")
	}
	return i.Scanner.Text()
}
func (i *Iost) Atoi(s string) int                 { x, _ := strconv.Atoi(s); return x }
func (i *Iost) GetNextInt() int                   { return i.Atoi(i.Text()) }
func (i *Iost) Atoi64(s string) int64             { x, _ := strconv.ParseInt(s, 10, 64); return x }
func (i *Iost) GetNextInt64() int64               { return i.Atoi64(i.Text()) }
func (i *Iost) Atof64(s string) float64           { x, _ := strconv.ParseFloat(s, 64); return x }
func (i *Iost) GetNextFloat64() float64           { return i.Atof64(i.Text()) }
func (i *Iost) Print(x ...interface{})            { fmt.Fprint(i.Writer, x...) }
func (i *Iost) Printf(s string, x ...interface{}) { fmt.Fprintf(i.Writer, s, x...) }
func (i *Iost) Println(x ...interface{})          { fmt.Fprintln(i.Writer, x...) }
func isLocal() bool                               { return os.Getenv("NICKEL") == "BACK" }
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	if isLocal() {
		fp, _ = os.Open(os.Getenv("WELL_EVERYBODY_LIES_TOO_MUCH"))
	}
	iost = NewIost(fp, wfp)
	defer func() {
		iost.Writer.Flush()
	}()
	solve()
}
func solve() {
	n := iost.GetNextInt()
	pp := make([]int, n)
	for i := 0; i < n; i++ {
		pp[i] = iost.GetNextInt() - 1
	}
	f := NewFenwickTree[int](n)
	ans := 0
	for i := 0; i < n; i++ {
		ans += sum(i)
		ans -= sum(f.Sum(0, pp[i]))
		f.Add(pp[i], 1)
	}
	iost.Println(ans)
}
func sum(i int) int {
	return i * (i + 1) / 2
}

type FenwickTree[T ~int | ~int64 | ~float64] []T

func NewFenwickTree[T ~int | ~int64 | ~float64](n int) FenwickTree[T] {
	return make(FenwickTree[T], n)
}

func (f FenwickTree[T]) Add(p int, x T) {
	for p++; p <= len(f); p += p & -p {
		f[p-1] += x
	}
}
func (f FenwickTree[T]) Sum(l, r int) T {
	return f.sum(r) - f.sum(l)
}
func (f FenwickTree[T]) sum(r int) T {
	var s T
	for ; r > 0; r -= r & -r {
		s += f[r-1]
	}
	return s
}

Java solution:
import static java.lang.Math.*;
import static java.util.Arrays.*;

import java.io.*;
import java.lang.reflect.*;
import java.util.*;
import java.util.ArrayList;
import java.util.concurrent.*;
import java.util.function.*;

public class Main{
  public static void main(String[] args) throws Exception{
    MyReader in = new MyReader(System.in);
    MyWriter out = new MyWriter(System.out,false),log = new MyWriter(System.err,true);
    int T = Solver.multi ? in.it() : 1;
    while (T-- > 0)
      Optional.ofNullable(new Solver(in,out,log).solve()).ifPresent(out::println);
    out.flush();
  }
}

class Solver extends BaseSolver{
  public Solver(MyReader in,MyWriter out,MyWriter log){ super(in,out,log); }

  public static boolean multi = false;

  public Object solve(){
    int N = in.it();
    int[] P = in.idx(N);
    int[] rev = new int[N];
    for (int i = 0;i < N;i++)
      rev[P[i]] = i;
    BIT bit = new BIT(N);
    for (int i = 0;i < N;i++)
      bit.upd(i,1);

    long ans = 0;

    for (int p = N -1;p >= 0;p--) {
      int i = rev[p];
      bit.upd(i,-1);
      long n = bit.get(i,N);
      long l = bit.get(0,i);
      long tmp = (l +1 +l +n) *n /2;
      ans += tmp;
    }

    return ans;
  }

  private void log(int[] t){
    for (var i:t) {
      String s = Integer.toBinaryString(i);
      s = "0".repeat(5 -s.length()) +s;
      log.println(s);
    }

  }

  long invCnt(int[] a){
    a = copyOf(a,a.length);
    int[] b = new int[a.length];
    int d = 1;
    long ret = 0;

    while (d < a.length) {
      System.arraycopy(a,0,b,0,a.length);
      for (int l = 0;l +d < a.length;l += d <<1) {
        int ai = l;
        int bi = l;
        int ci = l +d;
        int r = min(a.length,l +2 *d);
        while (ai < r)
          if (ci == r || bi < l +d && b[bi] <= b[ci])
            a[ai++] = b[bi++];
          else {
            ret += l +d -bi;
            a[ai++] = b[ci++];
          }
      }
      d <<= 1;
    }

    return ret;
  }

  void reverse(Object arr){
    if (!arr.getClass().isArray())
      throw new UnsupportedOperationException("reverse");

    int l = 0;
    int r = Array.getLength(arr) -1;

    while (l < r) {
      Object t = Array.get(arr,l);
      Array.set(arr,l,Array.get(arr,r));
      Array.set(arr,r,t);
      l++;
      r--;
    }

  }

  private int[][] rle(int[] S){
    List<int[]> list = new ArrayList<>();

    int[] cur = {S[0], 1};
    for (int i = 1;i < S.length;i++)
      if (cur[0] == S[i])
        cur[1]++;
      else {
        list.add(cur);
        cur = new int[]{S[i], 1};
      }

    list.add(cur);
    return list.stream().toArray(n -> new int[n][]);
  }
}

class BIT{
  public int n;
  private long[] bit;

  public BIT(int n){ this(new long[n]); }

  public BIT(long[] A){
    n = A.length;
    bit = new long[n +1];
    for (int i = 1;i <= n;i++) {
      bit[i] += A[i -1];
      if (i +(i &-i) <= n)
        bit[i +(i &-i)] += bit[i];
    }
  }

  public void upd(int x,long v){
    for (x++;x <= n;x += x &-x)
      bit[x] += v;
  }

  public long sum(int x){
    long ret = 0;
    for (;x > 0;x -= x &-x)
      ret += bit[x];
    return ret;
  }

  public long get(int i){ return get(i,i +1); }

  public long get(int l,int r){ return sum(r) -sum(l); }
}

abstract class RelationalUnionFind<F> extends UnionFind{
  private F[] dist;

  @SuppressWarnings("unchecked")
  public RelationalUnionFind(int n){
    super(n);
    dist = (F[]) new Object[n];
    setAll(dist,i -> id());
  }

  protected abstract F id();
  protected abstract F comp(F a,F b);
  protected abstract F inv(F v);
  protected abstract boolean eq(F a,F b);

  @Override
  public int root(int x){
    if (dat[x] < 0)
      return x;

    int r = root(dat[x]);
    dist[x] = comp(dist[dat[x]],dist[x]);

    return dat[x] = r;
  }

  public boolean valid(int u,int v,F c){ return !same(u,v) || eq(dist(u,v),c); }

  @Deprecated
  @Override
  public boolean unite(int u,int v){ return unite(u,v,id()); }

  public boolean unite(int u,int v,F f){
    if (!valid(u,v,f))
      return false;
    if (same(u,v))
      return true;
    f = comp(dist(u),f);
    f = comp(f,inv(dist(v)));
    super.unite(u = root(u),v = root(v));
    if (dat[u] > dat[v])
      dist[u] = inv(f);
    else
      dist[v] = f;
    return true;
  }

  public F dist(int x){
    root(x);
    return dist[x];
  }

  public F dist(int u,int v){ return !same(u,v) ? null : comp(inv(dist(u)),dist(v)); }
}

class Permutation{
  private int n;
  int[] arr;

  public Permutation(int n){ arr = Util.arrI(this.n = n,i -> i); }

  public Permutation(int[] arr){ this.arr = copyOf(arr,n = arr.length); }

  public boolean increment(){ return crement(1); }

  public boolean decrement(){ return crement(-1); }

  private boolean crement(int d){
    int l = n -2;
    while (0 <= l && arr[l] *d >= arr[l +1] *d)
      l--;

    if (l < 0)
      return false;

    int r = n -1;
    while (arr[l] *d >= arr[r] *d)
      r--;
    swap(l,r);

    l++;
    r = n -1;
    while (l < r)
      swap(l++,r--);

    return true;
  }

  private void swap(int l,int r){
    arr[l] ^= arr[r];
    arr[r] ^= arr[l];
    arr[l] ^= arr[r];
  }
}

class PrefixSum{
  private long[] sum;
  private int i;

  public PrefixSum(int n){ sum = new long[n +1]; }

  public PrefixSum(long[] a){
    this(a.length);
    for (int i = 0;i < a.length;i++)
      sum[i +1] = sum[i] +a[i];
  }

  public void add(long a){ sum[i +1] = sum[i++] +a; }

  public long get(int l,int r){ return sum[r] -sum[l]; }

  public long get(int i){ return get(i,i +1); }
}

class UnionFind{
  int num;
  protected int[] dat;
  protected int[] nxt;

  public UnionFind(int n){
    dat = new int[n];
    nxt = new int[n];
    setAll(nxt,i -> i);
    fill(dat,-1);
    num = n;
  }

  public int root(int x){ return dat[x] < 0 ? x : (dat[x] = root(dat[x])); }

  public boolean same(int u,int v){ return root(u) == root(v); }

  public boolean unite(int u,int v){
    if ((u = root(u)) == (v = root(v)))
      return false;

    if (dat[u] > dat[v]) {
      u ^= v;
      v ^= u;
      u ^= v;
    }
    dat[u] += dat[v];
    dat[v] = u;
    num--;
    nxt[u] ^= nxt[v];
    nxt[v] ^= nxt[u];
    nxt[u] ^= nxt[v];
    return true;
  }

  public int size(int x){ return -dat[root(x)]; }

  public int[] getGroup(int x){
    int[] ret = new int[size(x)];
    for (int i = 0,c = root(x);i < ret.length;i++)
      ret[i] = c = nxt[c];
    return ret;
  }
}

abstract class MonoidUnionFind<V> extends UnionFind{
  private V[] val;

  public MonoidUnionFind(int n){
    super(n);
    val = Util.cast(new Object[n]);
    setAll(val,this::init);
  }

  protected abstract V init(int i);
  protected abstract V agg(V a,V b);

  @Override
  public boolean unite(int u,int v){
    if ((u = root(u)) == (v = root(v)))
      return false;

    if (dat[u] > dat[v]) {
      u ^= v;
      v ^= u;
      u ^= v;
    }
    val[u] = agg(val[u],val[v]);

    return super.unite(u,v);
  }

  public V val(int i){ return val[root(i)]; }
}

class FastSet{
  private int size;
  private long[][] data = new long[1][1];

  public FastSet(){ this(1 <<18); }

  public FastSet(int n){ grow(n); }

  private void grow(int n){
    int K = (37 -Integer.numberOfLeadingZeros((n = max(data[0].length <<7,n)) -1)) /6;
    long[][] newData = new long[K][];
    for (int i = 0;i < data.length;i++)
      newData[i] = copyOf(data[i],n = n +63 >>6);
    for (int i = data.length;i < K;i++) {
      newData[i] = new long[n = n +63 >>6];
      for (int j = 0;j < newData[i -1].length;j++)
        if (newData[i -1][j] != 0)
          newData[i][j >>6] |= 1L <<j;
    }
    data = newData;
  }

  public boolean get(int x){ return x >>6 < data[0].length && (data[0][x >>6] >>>(x &63) &1) == 1; }

  public void set(int x){
    if (data[0].length <= x >>6)
      grow(x +1);
    if (get(x))
      return;
    size++;
    for (int i = 0;i < data.length;x >>= 6)
      data[i++][x >>6] |= 1L <<x;
  }

  public void clear(int x){
    if (!get(x))
      return;
    size--;
    long lastValue = 0;
    for (int i = 0;i < data.length && lastValue == 0;x >>= 6)
      lastValue = data[i++][x >>6] &= ~(1L <<x);
  }

  public int floor(int x){
    if (x < 0)
      return -1;
    if (get(x))
      return x;
    for (int i = 0,y = x;i < data.length;i++) {
      int offset = y &63;
      y >>= 6;
      long headMask = offset == 0 ? 0 : -1L >>>64 -offset;
      if (y < data[i].length && (data[i][y] &headMask) != 0)
        return last(i -1,y <<6 |highestOneBitOffset(data[i][y] &headMask));
    }
    return -1;
  }

  public int ceiling(int x){
    if (data[0].length <= x >>6)
      return -1;
    if (get(x))
      return x;
    for (int i = 0,y = x;i < data.length;i++) {
      int offset = y &63;
      y >>= 6;
      long tailMask = offset == 63 ? 0 : -1L <<1 +offset;
      if ((data[i][y] &tailMask) != 0)
        return first(i -1,y <<6 |lowestOneBitOffset(data[i][y] &tailMask));
    }
    return -1;
  }

  public int size(){ return size; }

  private int last(int i,int x){
    while (0 <= i)
      x = x <<6 |highestOneBitOffset(data[i--][x]);
    return x;
  }

  private int first(int i,int x){
    while (0 <= i)
      x = x <<6 |lowestOneBitOffset(data[i--][x]);
    return x;
  }

  private int highestOneBitOffset(long x){ return 63 -Long.numberOfLeadingZeros(x); }

  private int lowestOneBitOffset(long x){ return Long.numberOfTrailingZeros(x &-x); }

  public int[] toArray(){
    if (size == 0)
      return new int[0];
    int[] ret = new int[size];
    ret[0] = first(data.length -1,0);
    for (int i = 1;i < size;i++)
      ret[i] = ceiling(ret[i -1] +1);
    return ret;
  }
}

class Data extends BaseV{
  long v;

  public Data(long v){ this.v = v; }
}

class Edge<L> {
  public int id,u,v;
  public L val;
  public Edge<L> re;

  public Edge(int id,int u,int v,L val){
    this.id = id;
    this.u = u;
    this.v = v;
    this.val = val;
  }
}

class Graph<L> {
  protected int n;
  protected MyList<Edge<L>> es;
  private Edge<L>[][] go,bk;
  private int[] cntgo,cntbk;
  private boolean built;

  public Graph(int n,boolean dir){
    this.n = n;
    go = Util.cast(new Edge[n][]);
    bk = dir ? Util.cast(new Edge[n][]) : go;
    fill(go,new Edge[0]);
    fill(bk,new Edge[0]);
    es = new MyList<>();
    cntgo = new int[n];
    cntbk = dir ? new int[n] : cntgo;
  }

  public int size(){ return n; }

  protected L inv(L l){ return l; }

  public void addEdge(int u,int v){ addEdge(u,v,null); }

  public void addEdge(int u,int v,L l){
    var e = new Edge<>(es.size(),u,v,l);
    var re = new Edge<>(e.id,e.v,e.u,inv(e.val));
    es.add(e);
    re.re = e;
    e.re = re;
  }

  public Edge<L>[] go(int u){
    if (!built)
      build();
    return go[u];
  }

  public Edge<L>[] bk(int u){
    if (!built)
      build();
    return bk[u];
  }

  private void build(){
    for (var e:es) {
      cntgo[e.u]++;
      cntbk[e.v]++;
    }
    for (var e:es) {
      if (go[e.u].length == 0)
        go[e.u] = Util.cast(new Edge[cntgo[e.u]]);
      if (bk[e.v].length == 0)
        bk[e.v] = Util.cast(new Edge[cntbk[e.v]]);
    }
    for (var e:es) {
      go[e.u][--cntgo[e.u]] = e;
      bk[e.v][--cntbk[e.v]] = e.re;
    }
    built = true;
  }

  public void clear(){
    Edge<L>[] empty = Util.cast(new Edge[0]);
    for (var e:es)
      go[e.u] = bk[e.v] = empty;
    es.clear();
    built = false;
  }
}

abstract class BaseV{
  public int sz;
  public boolean fail;
}

class MyList<E> implements Iterable<E>{
  private E[] arr;
  private int hd,tl;

  public MyList(){ this(16); }

  public MyList(int n){ arr = Util.cast(new Object[Integer.highestOneBit(max(16,n) -1) <<1]); }

  public MyList(MyList<E> org){
    this(org.size() +1);
    System.arraycopy(org.arr,0,arr,0,tl = org.size());
  }

  public MyList(Collection<E> col){
    this(col.size() +1);
    col.forEach(this::add);
  }

  public void add(E t){ addLast(t); }

  public void addFirst(E e){
    hd = hd -1 &arr.length -1;
    arr[hd] = e;
    if (hd == tl)
      grow();
  }

  public void addLast(E e){
    arr[tl] = e;
    tl = tl +1 &arr.length -1;
    if (hd == tl)
      grow();
  }

  public E peek(){ return peekFirst(); }

  public E peekFirst(){ return arr[hd]; }

  public E peekLast(){ return arr[tl -1 &arr.length -1]; }

  public E poll(){ return pollFirst(); }

  public E pollFirst(){
    E ret = arr[hd];
    hd = hd +1 &arr.length -1;
    return ret;
  }

  public E pollLast(){
    tl = tl -1 &arr.length -1;
    return arr[tl];
  }

  public E get(int i){ return arr[hd +i &arr.length -1]; }

  public E remove(int i){
    i = hd +i &arr.length -1;
    E ret = arr[i];
    tl = tl -1 &arr.length -1;
    while (i != tl) {
      arr[i] = arr[i +1 &arr.length -1];
      i = i +1 &arr.length -1;
    }
    return ret;
  }

  public E removeFast(int i){
    swap(i,size() -1);
    return pollLast();
  }

  public void swap(int i,int j){
    i = hd +i &arr.length -1;
    j = hd +j &arr.length -1;
    Util.swap(arr,i,j);
  }

  public void set(int i,E t){ arr[hd +i &arr.length -1] = t; }

  public void clear(){ tl = hd; }

  public int size(){ return tl -hd &arr.length -1; }

  public boolean isEmpty(){ return tl == hd; }

  public void sort(){ sort(Util.cast(Comparator.naturalOrder())); }

  public void sort(Comparator<E> cmp){
    if (hd > tl)
      System.arraycopy(arr,hd,arr,tl,arr.length -hd);
    else
      System.arraycopy(arr,hd,arr,0,tl -hd);

    Arrays.sort(arr,hd = 0,tl = size(),cmp);
  }

  public <U> MyList<U> map(Function<E, U> func){
    MyList<U> ret = new MyList<>(size());
    forEach(t -> ret.add(func.apply(t)));
    return ret;
  }

  public MyList<E> rev(){
    MyList<E> ret = new MyList<>(size());
    for (int i = size();i-- > 0;)
      ret.add(get(i));
    return ret;
  }

  public int[] toIntArray(ToIntFunction<E> f){ return Util.arrI(size(),i -> f.applyAsInt(get(i))); }

  public E[] toArray(){
    if (hd == tl)
      return Util.cast(new Object[0]);
    E[] ret = Util.cast(Array.newInstance(arr[0].getClass(),size()));
    if (hd < tl)
      System.arraycopy(arr,hd,ret,0,tl -hd);
    else {
      System.arraycopy(arr,hd,ret,0,arr.length -hd);
      System.arraycopy(arr,0,ret,arr.length -hd,tl);
    }
    return ret;
  }

  private void grow(){
    E[] newarr = Util.cast(new Object[arr.length <<1]);
    System.arraycopy(arr,hd,newarr,0,arr.length -hd);
    System.arraycopy(arr,0,newarr,arr.length -hd,tl);
    hd = 0;
    tl = arr.length;
    arr = newarr;
  }

  @Override
  public Iterator<E> iterator(){
    return new Iterator<>(){
      int i = 0;

      @Override
      public boolean hasNext(){ return i < size(); }

      @Override
      public E next(){ return get(i++); }
    };
  }
}

class BaseSolver extends Util{
  public MyReader in;
  public MyWriter out,log;

  public BaseSolver(MyReader in,MyWriter out,MyWriter log){
    this.in = in;
    this.out = out;
    this.log = log;
  }

  public int[][] addId(int[][] T){
    return arr(new int[T.length][],i -> {
      int[] t = copyOf(T[i],T[i].length +1);
      t[t.length -1] = i;
      return t;
    });
  }

  public long inv(long x){ return pow(x,mod -2); }

  public long inv(long x,long mod){ return (extendGcd(x,mod)[0] +mod) %mod; }

  public long pow(long x,long n){ return pow(x,n,mod); }

  public long pow(long x,long n,long mod){
    long ret = 1;
    for (x %= mod;0 < n;x = x *x %mod,n >>= 1)
      if ((n &1) == 1)
        ret = ret *x %mod;
    return ret;
  }

  public int bSearchI(int o,int n,IntPredicate judge){
    for (int m = 0;1 < abs(n -o);)
      m = judge.test(m = o +n >>1) ? (o = m) : (n = m);
    return o;
  }

  public long bSearchL(long o,long n,LongPredicate judge){
    for (long m = 0;1 < abs(n -o);)
      m = judge.test(m = o +n >>1) ? (o = m) : (n = m);
    return o;
  }

  public double bSearchD(double o,double n,DoublePredicate judge){
    for (double m,c = 0;c < 100;c++)
      m = judge.test(m = (o +n) /2) ? (o = m) : (n = m);
    return o;
  }

  public long gcd(long a,long b){
    while (0 < b) {
      long t = a;
      a = b;
      b = t %b;
    }
    return a;
  }

  public long[] extendGcd(long a,long b){
    long x0 = 1,y0 = 0,x1 = 0,y1 = 1;
    while (b != 0) {
      long q = a /b,t = a %b,tx = x1,ty = y1;
      a = b;
      b = t;
      x1 = x0 -q *x1;
      y1 = y0 -q *y1;
      x0 = tx;
      y0 = ty;
    }
    return new long[]{x0, y0, a};
  }

  public long lcm(long a,long b){ return b /gcd(a,b) *a; }

  public long ceil(long a,long b){ return (a +b -1) /b; }

  public int[] lis(int[] arr){
    int n = arr.length;
    int[] lis = new int[n],idx = new int[n],par = new int[n];
    fill(lis,infI);

    int l = 0;
    for (int i = 0;i < n;i++) {
      int a = arr[i];
      int pos = bSearchI(n -1,-1,ii -> lis[ii] >= a);
      lis[pos] = a;
      idx[pos] = i;
      if (pos > 0)
        par[i] = idx[pos -1];
      l = max(l,pos +1);
    }

    int[] result = new int[l];
    for (int i = l -1,cur = idx[l -1];i >= 0;i--) {
      result[i] = arr[cur];
      cur = par[cur];
    }
    return result;
  }

  public int min(int... arr){
    int ret = arr[0];
    for (int i = 1;i < arr.length;i++)
      ret = Math.min(ret,arr[i]);
    return ret;
  }

  public long min(long... arr){
    long ret = arr[0];
    for (int i = 1;i < arr.length;i++)
      ret = Math.min(ret,arr[i]);
    return ret;
  }

  public double min(double... arr){
    double ret = arr[0];
    for (int i = 1;i < arr.length;i++)
      ret = Math.min(ret,arr[i]);
    return ret;
  }

  public int max(int... arr){
    int ret = arr[0];
    for (int i = 1;i < arr.length;i++)
      ret = Math.max(ret,arr[i]);
    return ret;
  }

  public long max(long... arr){
    long ret = arr[0];
    for (int i = 1;i < arr.length;i++)
      ret = Math.max(ret,arr[i]);
    return ret;
  }

  public double max(double... arr){
    double ret = arr[0];
    for (int i = 1;i < arr.length;i++)
      ret = Math.max(ret,arr[i]);
    return ret;
  }
}

class Util{
  public static String yes = "Yes",no = "No";
  public static int infI = (1 <<30) -1;
  public static long infL = (1L <<61 |1 <<30) -1,
      mod = 998244353;
  public static Random rd = ThreadLocalRandom.current();
  private long st = System.currentTimeMillis();

  protected long elapsed(){ return System.currentTimeMillis() -st; }

  protected void reset(){ st = System.currentTimeMillis(); }

  public static int[] arrI(int N,IntUnaryOperator f){
    int[] ret = new int[N];
    setAll(ret,f);
    return ret;
  }

  public static long[] arrL(int N,IntToLongFunction f){
    long[] ret = new long[N];
    setAll(ret,f);
    return ret;
  }

  public static double[] arrD(int N,IntToDoubleFunction f){
    double[] ret = new double[N];
    setAll(ret,f);
    return ret;
  }

  public static <T> T[] arr(T[] arr,IntFunction<T> f){
    setAll(arr,f);
    return arr;
  }

  @SuppressWarnings("unchecked")
  public static <T> T cast(Object obj){ return (T) obj; }

  public static <T> void swap(T[] arr,int i,int j){
    T t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
  }
}

class MyReader{
  private byte[] buf = new byte[1 <<16];
  private int ptr,tail;
  private InputStream in;

  public MyReader(InputStream in){ this.in = in; }

  private byte read(){
    if (ptr == tail)
      try {
        tail = in.read(buf);
        ptr = 0;
      } catch (IOException e) {}
    return buf[ptr++];
  }

  private boolean isPrintable(byte c){ return 32 < c && c < 127; }

  private byte nextPrintable(){
    byte ret = read();
    while (!isPrintable(ret))
      ret = read();
    return ret;
  }

  public int it(){ return toIntExact(lg()); }

  public int[] it(int N){ return Util.arrI(N,i -> it()); }

  public int[][] it(int H,int W){ return Util.arr(new int[H][],i -> it(W)); }

  public int idx(){ return it() -1; }

  public int[] idx(int N){ return Util.arrI(N,i -> idx()); }

  public int[][] idx(int H,int W){ return Util.arr(new int[H][],i -> idx(W)); }

  public long lg(){
    byte i = nextPrintable();
    boolean negative = i == 45;
    long n = negative ? 0 : i -'0';
    while (isPrintable(i = read()))
      n = 10 *n +i -'0';
    return negative ? -n : n;
  }

  public long[] lg(int N){ return Util.arrL(N,i -> lg()); }

  public long[][] lg(int H,int W){ return Util.arr(new long[H][],i -> lg(W)); }

  public double dbl(){
    String str = str();
    return Double.parseDouble(str);
  }

  public double[] dbl(int N){ return Util.arrD(N,i -> dbl()); }

  public double[][] dbl(int H,int W){ return Util.arr(new double[H][],i -> dbl(W)); }

  public char[] ch(){ return str().toCharArray(); }

  public char[][] ch(int H){ return Util.arr(new char[H][],i -> ch()); }

  public String line(){
    StringBuilder sb = new StringBuilder();
    for (byte c;(c = read()) != '\n';)
      sb.append((char) c);
    return sb.toString();
  }

  public String str(){
    StringBuilder sb = new StringBuilder();
    sb.append((char) nextPrintable());
    for (byte c;isPrintable(c = read());)
      sb.append((char) c);
    return sb.toString();
  }

  public String[] str(int N){ return Util.arr(new String[N],i -> str()); }

  public String[][] str(int H,int W){ return Util.arr(new String[H][],i -> str(W)); }
}

class MyWriter{
  private OutputStream out;
  private byte[] buf = new byte[1 <<16],ibuf = new byte[20];
  private int tail;
  private boolean autoflush;

  public MyWriter(OutputStream out,boolean autoflush){
    this.out = out;
    this.autoflush = autoflush;
  }

  public void flush(){
    try {
      out.write(buf,0,tail);
      tail = 0;
    } catch (IOException e) {
      e.printStackTrace();
    }
  }

  private void write(byte b){
    buf[tail++] = b;
    if (tail == buf.length)
      flush();
  }

  private void write(long n){
    if (n < 0) {
      n = -n;
      write((byte) '-');
    }
    int i = ibuf.length;
    do {
      ibuf[--i] = (byte) (n %10 +'0');
      n /= 10;
    } while (n > 0);
    while (i < ibuf.length)
      write(ibuf[i++]);
  }

  private void print(Object obj){
    if (obj instanceof Boolean)
      print((boolean) obj ? Util.yes : Util.no);
    else if (obj instanceof Integer)
      write((int) obj);
    else if (obj instanceof Long)
      write((long) obj);
    else if (obj instanceof char[])
      for (char b:(char[]) obj)
        write((byte) b);
    else if (obj.getClass().isArray()) {
      int l = Array.getLength(obj);
      for (int i = 0;i < l;i++) {
        print(Array.get(obj,i));
        if (i +1 < l)
          write((byte) ' ');
      }
    } else
      print(Objects.toString(obj).toCharArray());
  }

  public void println(Object obj){
    if (obj == null)
      obj = "null";
    if (obj instanceof Iterable<?>)
      for (Object e:(Iterable<?>) obj)
        println(e);
    else if (obj.getClass().isArray() && Array.getLength(obj) > 0 && Array.get(obj,0).getClass().isArray()) {
      int l = Array.getLength(obj);
      for (int i = 0;i < l;i++)
        println(Array.get(obj,i));
    } else {
      print(obj);
      write((byte) '\n');
      if (autoflush)
        flush();
    }
  }

  public void printlns(Object... obj){
    print(obj);
    write((byte) '\n');
    if (autoflush)
      flush();
  }
}

JavaScript solution:
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextssort(n,a){return a?cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>b-a):cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>a-b);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}
var streams=[];function print(s){streams.push(s);}

class BIT{//1-indexed
  constructor(n){
    this.a = Array(n+1).fill(0);
  }
  add(val,id){
    for(var i=id,a=this.a;i<a.length;i+=i&-i)a[i]+=val;
  }
  get(id){
    for(var r=0,i=id;i;i-=i&-i)r+=this.a[i];
    return r;
  }
  range(l,r){//[l,r]
    return this.get(r) - this.get(l-1);
  }
}


var myOut = main();
if(myOut !== undefined)console.log(String(myOut));
if(streams.length)console.log(streams.join("\n"));

function main(){
  var q = 1;
  while(q--)print(solve());
}

function solve(){
  var n = next();
  var ans = 0;
  var bi = new BIT(n+1);
  for(var i = 0; i < n; i++){
    var p = next();
    var t = bi.range(p+1,n+1);
    ans += f(i) - f(i-t);
    bi.add(1,p);
  }
  return ans;
}

function f(a){
  return a * (a+1) / 2;
}

Python solution:
import sys, random
input = lambda : sys.stdin.readline().rstrip()


write = lambda x: sys.stdout.write(x+"\n"); writef = lambda x: print("{:.12f}".format(x))
debug = lambda x: sys.stderr.write(x+"\n")
YES="Yes"; NO="No"; pans = lambda v: print(YES if v else NO); INF=10**18
LI = lambda v=0: list(map(lambda i: int(i)-v, input().split())); II=lambda : int(input()); SI=lambda : [ord(c)-ord("a") for c in input()]
def debug(_l_):
    for s in _l_.split():
        print(f"{s}={eval(s)}", end=" ")
    print()
def dlist(*l, fill=0):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [dlist(*ll, fill=fill) for _ in range(l[0])]

class BIT:
    ### BIT binary
    def __init__(self, n, values=None):
        self.bit = [0]*(n+1)
        self.n = n
        self.total = 0
        if values is not None:
            for i,v in enumerate(values):
                self.add(i,v)
                self.total += v
    def check(self):
        l = []
        prv = 0
        for i in range(1,self.n+1):
            val = self.query(i)
            l.append(val-prv)
            prv = val
        print(" ".join(map(str, l)))
    #a1 ~ aiまでの和 O(logn)
    def query(self,i):
        res = 0
        while i > 0:
            res += self.bit[i]
            # res %= M
            i -= i&(-i)
        return res
    def get(self,i):
        return self.query(i+1) - self.query(i)
    #ai += x(logN)
    def add(self,i,x):
        i += 1
        if i==0:
            raise RuntimeError
        self.total += x
        while i <= self.n:
            self.bit[i] += x
            # self.bit[i] %= M
            i += i&(-i)
    def index(self, v):
        """a0,...,aiの和がv以上になる最小のindexを求める
        存在しないとき配列サイズを返す
        """
        if v <= 0:
            return 0
        if self.total<v:
            return self.n
        x = 0
        r = 1
        while r < self.n:
            r = r << 1;
        ll = r
        while ll>0:
            if x+ll<self.n and self.bit[x+ll]<v:
                v -= self.bit[x+ll]
                x += ll
            ll = ll>>1
        return x

n = int(input())
p = LI(1)
bit = BIT(n)
ans = 0
total = 0
for i in range(0,n):
    # [0,i) に i を挿入
    num = total - bit.query(p[i])
    # i, ... i-(num-1) の和
    val = i*num - num * (num-1) // 2
    # print(i, num, val)
    ans += val
    bit.add(p[i], 1)
    total += 1
print(ans)

Ruby solution:
# Fenwick Tree
class FenwickTree
  attr_reader :data, :size

  def initialize(arg)
    case arg
    when Array
      @size = arg.size
      @data = [0].concat(arg)
      (1 ... @size).each do |i|
        up = i + (i & -i)
        next if up > @size

        @data[up] += @data[i]
      end
    when Integer
      @size = arg
      @data = Array.new(@size + 1, 0)
    else
      raise ArgumentError.new("wrong argument. type is Array or Integer")
    end
  end

  def add(i, x)
    i += 1
    while i <= @size
      @data[i] += x
      i += (i & -i)
    end
  end

  # .sum(l, r)  # [l, r)  <- Original
  # .sum(r)     # [0, r)  <- [Experimental]
  # .sum(l..r)  # [l, r]  <- [Experimental]
  def sum(a, b = nil)
    if b
      _sum(b) - _sum(a)
    elsif a.is_a?(Range)
      l = a.begin
      l += @size if l < 0
      if r = a.end
        r += @size if r < 0
        r += 1 unless a.exclude_end?
      else
        r = @size
      end
      _sum(r) - _sum(l)
    else
      _sum(a)
    end
  end

  def _sum(i)
    res = 0
    while i > 0
      res += @data[i]
      i &= i - 1
    end
    res
  end
  alias left_sum _sum

  def to_s
    "<#{self.class}: @size=#{@size}, (#{@data[1..].join(', ')})>"
  end
end


n=gets.to_i
a=gets.split.map(&:to_i).map{_1-1}
# n=200000
# a=[*0..n-1].reverse
c=0
f=FenwickTree.new(n)
def cs(l,n)
  ((l+n)*((l+n)+1)/2)-((l)*(l+1)/2)
end
a.each_with_index do |a,i|
  cc=f.sum(a,n)
  ii=f.sum(0,a)
  c+=cs(a-(a-ii),cc)

  # c+=((cc+i-1)*((cc+i-1)+1)/2)-((i-1)*(i)/2)
  f.add(a,1)
  # p [a,c,cc,ii,cs(a-(a-ii),cc)]
end
puts c