#pragma GCC optimize("Ofast")
#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;
const int B = 1e5;
int len, cnt[450][B * 2 + 2];
deque < int > b[450];
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;
}
int lst = b[ll].back();
for(int i = l % len + 1; i < len; i++){
b[ll][i] = b[ll][i - 1];
}
b[ll][l % len] = b[rr][r % len];
cnt[ll][b[ll][l % len] + B]++;
cnt[ll][lst + B]--;
for(int i = ll + 1; i <= rr - 1; i++){
b[i].push_front(lst);
cnt[i][lst + B]++;
lst = b[i].back();
b[i].pop_back();
cnt[i][lst + B]--;
}
cnt[rr][lst + B]++;
cnt[rr][b[rr][r % len] + B]--;
deque < int > y = {lst};
for(int i = 1; i <= r % len; i++){
b[rr][i] = b[rr][i - 1];
}
b[rr][0] = lst;
}
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 + B] > 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] + B]++;
}
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
*/
// int main() {
// int n;
// cin >> n;
// vector<int> S(2 * n);
// for (int i = 0; i < 2 * n; i++)
// cin >> S[i];
// fclose(stdin);
// long long result = count_swaps(S);
// printf("%lld\n", result);
// fclose(stdout);
// return 0;
// }
