#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 1;
struct segtree{
struct Node{
int mn, mx, lazy;
};
int size = 1;
vector<Node> stree;
void init(int n){
while(size <= n) size <<= 1;
stree.assign(4*size, {N, -N, -N});
}
void push(int x, int lx, int rx){
if(rx - lx == 1 || stree[x].lazy == -N) return;
stree[2*x+1].lazy = stree[2*x+1].mn = stree[2*x+1].mx = stree[x].mx;
stree[2*x+2].lazy = stree[2*x+2].mn = stree[2*x+2].mx = stree[x].mx;
stree[x].lazy = -N;
}
void upd(int l, int r, int v, int x, int lx, int rx){
push(x, lx, rx);
if(lx >= r || rx <= l) return;
if(lx >= l && rx <= r) {
stree[x].mx = stree[x].mn = stree[x].lazy = v;
return;
}
int m = (lx + rx) / 2;
upd(l, r, v, 2 * x + 1, lx, m);
upd(l, r, v, 2 * x + 2, m, rx);
stree[x].mx = max(stree[2*x+1].mx, stree[2*x+2].mx);
stree[x].mn = min(stree[2*x+1].mn, stree[2*x+2].mn);
}
int qry_mn(int l, int x, int lx, int rx){
push(x, lx, rx);
if(rx <= l) return -1;
if(stree[x].mn > 0) return -1;
if(rx - lx == 1){
return lx;
}
int m = (lx + rx) / 2;
int res = qry_mn(l, 2 * x + 1, lx, m);
if(res == -1) res = qry_mn(l, 2*x + 2, m, rx);
return res;
}
int qry_mx(int l, int x, int lx, int rx){
push(x, lx, rx);
if(rx <= l) return -1;
if(stree[x].mx < 0) return -1;
if(rx - lx == 1){
return lx;
}
int m = (lx + rx) / 2;
int res = qry_mx(l, 2 * x + 1, lx, m);
if(res == -1) res = qry_mx(l, 2*x + 2, m, rx);
return res;
}
void upd(int l, int r, int v){
upd(l, r, v, 0, 0, size);
}
int qry_mn(int l){
return qry_mn(l, 0, 0, size);
}
int qry_mx(int l){
return qry_mx(l, 0, 0, size);
}
} st;
long long count_swaps(std::vector<int> s) {
st.init(s.size() + 1);
int S = abs(s[0]);
for(int i = 0; i < s.size(); i++){
st.upd(i, i + 1, s[i]);
}
long long ans = 0;
for(int i = 0; i < s.size() - 1; i++){
if(i & 1){
int id = st.qry_mx(i);
ans += (id - i + 0ll);
st.upd(i + 1, id + 1, -S);
}else{
int id = st.qry_mn(i);
ans += (id - i + 0ll);
st.upd(i + 1, id + 1, S);
}
}
return ans;
}
