一道不错的贪心题，证明挺好玩。
我做这道题的时候首先是从前缀和来考虑的。如果 s_i 是第 i 个位置的前缀和，那么一个排列合法当且仅当 s_{2i}<0 且 s_{2i+1}=0，交换两个相邻数就等价于在前缀和的某一个位置上减少某一个数。然后就卡着了。
换一种思路，可以考虑贪心。直觉告诉我，如果每次都将当前排列中的第一个配对，那么最终结果一定最优。
证明如下：
定义“排列 p_1 对于排列 p_2 的逆序对”为一个元素对 (i,j)，使得在 p_1 中 i 在 j 前，p_2 中 i 在 j 后。
假设最终答案排列中当前排列的第一个不是配对在最前面，那么他一定配对在某个地方。设这个最终排列为 p_{ans}，当前排列为 p_{cur}。
然后我们将 $p_{cur}$ 中 $x$ 到 $x'$ 中的所有 $p_{cur}$ 关于 $p_{ans}$ 的逆序对消除（即排好序），然后所有在答案中出现在 $x$ 左边的元素一定在这中间部分的左边，将 $x$ 和 $x'$ 在中间配对，这样可以保证每一步交换都至少消除一个逆序对。容易证明这样做可行，且不会影响答案，也不会影响将 $p_{cur}$ 变为 $p_{ans}$ 的其余步骤。
在这种情况下，答案显然不劣于先排列完 $x$ 到 $x'$ 中的所有逆序对，再将 $x'$ 调换到最开头与 $x$ 配对。因为 $x$ 位于开头，将 $x$ 与 $x'$ 配对这一步不会耗费更多步数，并且配对完成之后也不需要担心干扰其余配对组。
那么答案也不劣于先将 $x$ 和 $x'$ 配对，再排列完那些逆序对。
然而先将 $x$ 和 $x'$ 配对后，原数列就可以忽略最前面的一对，变为一个长度为 $2n-2$ 的数列。也就是说，我们可以不需要排列那些逆序对，而直接递归求解。
最后的结论就是，每次将排列中的第一个配对，答案一定不劣于其余任何答案。
这个证明很好玩（qwq）。
引理2：如果有多个元素可以与最开头的配对，选择第一个，答案一定不劣。
这个很好证。如果最终答案是之后的元素和最开头的配对，那么我们先将第一个元素和最开头的配对，然后将后面的元素移到第一个元素的位置上。也就是说，“将第一个合适的元素与最开头的配对”一定可以成为其他所有策略的第一步。那就做呗。
然后是代码实现部分。需要找到对于每个元素与他最接近的匹配元素，还要维护他们的实时位置。这里我太菜了没想到用 `vector`，所以直接使用并查集来维护那个最接近的匹配元素。维护实时位置只需要用树状数组记录每次匹配对位置的影响就可以了。
附 AC 代码：
```cpp
#include <cstdio>
using namespace std;
int st[400005];
void init(int n)
{
for(int i=1; i<=n; ++i)
{
st[i] = i;
}
}
int getfa(int x)
{
return st[x]==x ? x : st[x]=getfa(st[x]);
}
void unio(int a,int b)
{
st[getfa(a)] = getfa(b);
}
int ti[200005];
int trin;
inline int lowbit(int x)
{
return x&(-x);
}
void fix(int x,int k)
{
while(x <= trin)
{
ti[x] += k;
x += lowbit(x);
}
}
int query(int x)
{
int res = 0;
while(x)
{
res += ti[x];
x -= lowbit(x);
}
return res;
}
int si[200005];
int pi[200005];
int lpil[200005];
int lpir[200005];
int cpyed[200005];
int main()
{
int n;
scanf("%d",&n);
for(int i=1; i<=2*n; ++i)
{
scanf("%d",si+i);
}
n *= 2;
trin = n;
init(2*n);
for(int i=n; i>=1; --i)
{
if(si[i] < 0)
{
if(lpir[-si[i]])
{
unio(i+n,lpir[-si[i]]);
}
if(lpil[-si[i]])
{
pi[i] = lpil[-si[i]];
}
lpil[-si[i]] = i;
}
else
{
if(lpil[si[i]])
{
unio(i+n,lpil[si[i]]);
}
if(lpir[si[i]])
{
pi[i] = lpir[si[i]];
}
lpir[si[i]] = i;
}
}
long long ans = 0;
for(int i=1; i<=n; ++i)
{
if(cpyed[i])
{
continue;
}
int cp = getfa(i+n);
int thpos = i+query(i);
int cppos = cp+query(cp);
ans += cppos-thpos-1 + (si[i]>0);
fix(i,1);
fix(cp,-1);
cpyed[cp] = 1;
unio(i,pi[i]);
unio(cp,pi[cp]);
}
printf("%lld",ans);
}
```