public class shoes {
// public static void main(String[] args) {
// int testData[] = { 2, -1, -2, 1 };
// System.out.println("total count: " +count_swaps(testData));
// }
static int[] a;
public shoes() {
}
// public shoes(int n) {
// a = new int[n];
// }
static int count(int right) {
int cnt = 0;
for (; right >= 0; right = (right & (right + 1)) - 1) {
cnt += a[right];
}
return cnt;
}
static int count(int left, int right) {
return count(right) - count(left - 1);
}
static void put(int index) {
for (; index < a.length; index = index | (index + 1)) {
a[index]++;
}
}
static int[] change(int[] v) {
int n = v.length / 2;
int cnt[] = new int[n];
// for (int i = 0; i<cnt.length; i++)
// cnt[i] = 0;
for (int i = 0; i < 2 * n; i++)
if (v[i] > 0)
cnt[v[i] - 1]++;
for (int i = 1; i < n; i++)
cnt[i] += cnt[i - 1];
int[] cntl = new int[cnt.length];//cnt, cntr = cnt;
int[] cntr = new int[cnt.length];
copyArray(cnt, cntl);
copyArray(cnt, cntr);
for (int i = 0; i < 2 * n; i++)
if (v[i] > 0)
v[i] = (--cntr[v[i] - 1]) + 1;
else
v[i] = -((--cntl[-v[i] - 1]) + 1);
return v;
}
static void copyArray(int[] a1,int[] a2) {
for (int i=0; i<a1.length; i++) {
a2[i] = a1[i];
}
}
static int[] create_index(int n, int[] S) {
int[] index = new int[2 * n + 1];
for (int i = 0; i < 2 * n; i++) {
index[S[i] + n] = i;
}
return index;
}
static long count_adjacent(int n, int[] S) {
int[] index = create_index(n, S);
// shoes f = new shoes(2 * n);
long ans = 0;
for (int i = 0; i < 2 * n; i++) {
if (S[i] != 0) {
int pos = index[-S[i] + n];
ans += pos - i - count(i, pos) - (S[i] < 0 ? 1 : 0);
S[pos] = 0;
put(pos);
}
}
return ans;
}
static long count_swaps(int[] S) {
S = change(S);
int n = S.length / 2;
a = new int[2*n];
// for (int i =0; i < a.length; i++)
// a[i] = 0;
return count_adjacent(n, S);
}
}
