#include <bits/stdc++.h> #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } using namespace std; #include "shoes.h" const int N = 2e5 + 5; int bit[N]; void upd(int pos, int val) { while(pos < N) { bit[pos] += val; pos += pos & -pos; } } int get(int pos) { int ret = 0; while(pos) { ret += bit[pos]; pos -= pos & -pos; } return ret; } bool marked[N]; int arr[N]; vector<int> occ[2 * N]; long long count_swaps(std::vector<int> s) { int n = (int)s.size() / 2; int m = 2 * n; long long ans = 0; int pos = 1; for(int i = 1; i <= m; i++) { arr[i] = s[i - 1]; } for(int i = m; i >= 1; i--) { occ[arr[i] + N].push_back(i); } for(int _ = 0; _ < n; _++) { while(marked[pos]) { pos += 1; } int num = arr[pos]; int target = -num; int where = occ[target + N].back(); marked[pos] = true; marked[where] = true; occ[target + N].pop_back(); occ[num + N].pop_back(); int cur_pos = where + (get(N - 1) - get(where)); ans += cur_pos - (2 * _ + 2); if(num > 0) ans += 1; upd(where, 1); } return ans; } //int main() { // ios_base::sync_with_stdio(false); // cin.tie(0), cout.tie(0); // // file("A") else file("task"); // // return 0; //}