#include <bits/stdc++.h> #include "shoes.h" using namespace std; const int N = 1e5; struct fenwick{ long long a[N]; void add(int x, int val) { for (; x < N; x += x & -x) { a[x] += val; } } long long get(int x) { long long res = 0; for (; x > 0; x -= x & -x) { res += a[x]; } return res; } }; long long count_swaps(vector<int> a) { int n = (int) a.size(); fenwick fenw; vector<pair<int, int>> b(n); for (int i = 0; i < n; i++) { b[i].first = a[i]; b[i].second = i + 1; } auto cmp = [&](pair<int, int> x, pair<int, int> y){ if (abs(x.first) != abs(y.first)) { return abs(x.first) > abs(y.first); } else { if (x.first != y.first) { return x.first < y.first; } return x.first < y.first; } }; sort(b.begin(), b.end(), cmp); /*for (int i = 0; i < n; i++) { cout << b[i].first << " " << b[i].second << '\n'; }*/ // 4, 1, 3, 2 // for (int i = 1; i <= n; i++) { fenw.a[i] = i - 1; } long long res = 0; for (int i = 0; i < n; i++) { res += fenw.get(b[i].second) - fenw.get(b[i].second - 1); fenw.add(1, 1); fenw.add(b[i].second, -1); } return res; } /*int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } cout << count_swaps(a) << '\n'; return 0; }*/