#include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; #define double long double #define int long long typedef vector VI; typedef pair pii; typedef vector VP; typedef vector VS; typedef priority_queue PQ; templatebool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } templatebool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } #define fore(i,a) for(auto &i:a) #define REP(i,n) for(int i=0;i, greater > q2; struct segtree { public: const int SIZE = 1 << 18; VI seg, lazy; //seg:区間の合計値 lazy:区間に対して、加える値でまだ遅延しているもの segtree() :seg(SIZE * 2), lazy(SIZE * 2) {} void lazy_evaluate(int k, int l, int r) { if (lazy[k] != 0) { seg[k] += lazy[k]; //区間[l,r)にすべて同じ値を追加することになっていて、 //segには合計値が入っているので、加える値を足す if (r - l > 1) { lazy[k * 2 + 1] += lazy[k]; lazy[k * 2 + 2] += lazy[k]; } lazy[k] = 0; } } void update(int a, int b, int k, int l, int r, int x) { lazy_evaluate(k, l, r); if (r <= a || b <= l)return; if (a <= l && r <= b) { lazy[k] += x; lazy_evaluate(k, l, r); } else { update(a, b, k * 2 + 1, l, (l + r) / 2, x); update(a, b, k * 2 + 2, (l + r) / 2, r, x); seg[k] = seg[k * 2 + 1] + seg[k * 2 + 2]; } } int query(int a, int b, int k, int l, int r) { lazy_evaluate(k, l, r); if (r <= a || b <= l)return 0; if (a <= l && r <= b)return seg[k]; int x = query(a, b, k * 2 + 1, l, (l + r) / 2); int y = query(a, b, k * 2 + 2, (l + r) / 2, r); return x + y; } void update(int a, int b, int x) { update(a, b, 0, 0, SIZE, x); } //update(a,b,x) := [a,b)を全てxを加える int query(int a, int b) { return query(a, b, 0, 0, SIZE); } //query(a,b) := [a,b)に対する合計値を求める }; signed main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; int ans = 0; VI M(N); segtree seg; REP(i, N)cin >> M[i]; REP(i, N) { //cout << i << " " << seg.query(M[i] - 1, M[i]) << endl; ans += seg.query(M[i]-1, M[i]); seg.update(0, M[i], 1); } cout << ans << endl; return 0; }