#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;
int len;
deque < int > b[500];
unordered_map < int , int > cnt[500];
void upd(int l, int r){
int ll = l / len, rr = r / len;
if(ll == rr){
deque < int > d;
for(int i = l % len; i <= r % len; i++)
d.push_back(b[ll][i]);
d.push_front(d.back());
d.pop_back();
int idx = 0;
for(int i = l % len; i <= r % len; i++)
b[ll][i] = d[idx++];
return;
}
deque < int > x = {b[rr][r % len]};
for(int i = l % len; i < len; i++){
x.push_back(b[ll][i]);
}
int _idx = 0;
for(int i = l % len; i < len; i++){
b[ll][i] = x[_idx++];
}
int lst = x.back();
cnt[ll][x.front()]++;
cnt[ll][lst]--;
for(int i = ll + 1; i <= rr - 1; i++){
b[i].push_front(lst);
cnt[i][lst]++;
lst = b[i].back();
b[i].pop_back();
cnt[i][lst]--;
}
deque < int > y = {lst};
for(int i = 0; i <= r % len; i++){
y.push_back(b[rr][i]);
}
cnt[rr][lst]++;
cnt[rr][y.back()]--;
int idx_ = 0;
for(int i = 0; i <= r % len; i++){
b[rr][i] = y[idx_++];
}
}
int ask(int l, int r, int x){
int ll = l / len, rr = r / len;
// cout << l << '-' << r << "<->" << ll << '-' << rr << endl;
if(ll == rr){
for(int i = l % len; i <= r % len; i++){
if(b[ll][i] == x){
return ll * len + i;
}
}
return l;
}
for(int i = l % len; i < len; i++){
if(b[ll][i] == x){
return ll * len + i;
}
}
// cout << "sonraki: ";
// for(auto i : b[ll + 1])cout << i << '-';cout << endl;
// cout << "dasssaqq: " << cnt[ll + 1][-9] << endl;
int idx = -1;
for(int i = ll + 1; i <= rr; i++){
if(cnt[i][x] > 0){
idx = i;
break;
}
}
if(idx != -1){
for(int i = 0; i < len; i++){
if(b[idx][i] == x){
return idx * len + i;
}
}
}
for(int i = 0; i <= r % len; i++){
if(b[rr][i] == x){
return rr * len + i;
}
}
return l;
}
long long count_swaps(vector < int > s){
int n = s.size();
len = sqrt(n + .0) + 1;
for(int i = 0; i < n; i++){
b[i / len].push_back(s[i]);
cnt[i / len][s[i]]++;
}
long long ans = 0;
for(int i = 0; i < n; i++){
int si = b[i / len][i % len], si_ = si;
if(i >= 1)
si_ = b[(i - 1) / len][(i - 1) % len];
if(si > 0 && i % 2 == 0){
int j = ask(i, n - 1, -si);
ans += (j - (i + 1) + 1);
// cout << i << '-' << j << "--" << si << endl;
upd(i, j);
}
else if(si < 0 && i % 2 == 1 || si > 0 && si != -si_){
int j = ask(i, n - 1, -si_);
ans += (j - (i + 1) + 1);
// cout << i << '-' << j << endl;
upd(i, j);
}
// for(int _ = 0; _ < len; _++){
// for(auto __ : b[_])cout << __ << ' ';
// }
// cout << endl;
}
return ans;
}
/*
4
-6 9 -9 6 7 -6 6 -7
*/
