楼上巨佬讲得太好了%%%%%orz

蒟蒻来加一些自己的理解。

首先对于有一些士兵，他们的在哪个队伍里其实是不相干的。

如下面的例子：（括号内为编号）

1(0) 2(1) 3(2)

1(3) 2(4) 3(5)

那么很显然，其实0与1，0与2，1与2等等等等之间怎么站是一点联系都没有、相互独立的。

而0和3，1和4，2和5是有关系的（它们永远站不到同一行）

那么对于任意数据，也可能能够分出很多个联通快，使得它们间互不相干。

那么对于每个联通块，我们都取最小的、能够使得联通块满足题意的值，加起来，就是答案了。

那么怎么求联通块内的最小值呢、、

借用楼上巨佬的话%%%

1.若相同的两个数字在同一行，第i列和第j列，则第i列和第j列中一定恰有一列需要交换，于是在点i和点j间连一条权值为1的边

2.若相同的两个数字不在同一行，在第i列和第j列，则第i列和第j列中一定要么都需要交换要么都不需要交换，于是在点i和点j间连一条权值为0的边

只需要在新图上进行二染色，使得权值为1的边两侧染色不同，权值为0的边两侧染色相同

那么边权的意思就是：如果边权为1，那么这个边所连接的点不应该在同一队伍里，也就是不应该是同一颜色的。

否则边权为0，那么两个点应该是同一个颜色的。

额外的，如果两个士兵站在同一列，那么这两个士兵不应该（也不可能）站在同一行里，应当连一条边为1。

于是我们对每一个联通块进行BFS黑白染色，那么对于同一行，它们的士兵的0，1值应该是一一相反的（因为同一列的士兵间有边权为1的边）

任务就成了：在一个联通块里，将权值为0（或者1，同理）的士兵换到同一行，最少需要几步？

又因为上下两行的士兵的0，1值一一相反，所以如果上面全是0或1，下面的“颜色”也就“纯”了。

那么我们只需要考虑第一行里的0、1值哪个出现的次数较小，然后交换就好了。

具体来说，如果我们有如下两行权值：

0 1 0 1 1 0 0 0 0 1 0 0 1

1 0 1 0 0 1 1 1 1 0 1 1 0

第一行中的1出现次数比第一行中0出现次数少，所以我们选择将第一行全部换为0，那么交换次数即第一行中1的出现次数，为5。

那么这样子我们就解决了一个联通块，把所有联通块的解加起来就是最后的答案了。

【虽然最后的结论很简单，代码量也不大，但是思维难度还是挺大的（毕竟蒟蒻orz orz）】

#include <cstdio>
#include <cstdlib>

#include <queue>

#define FOR_EDGE(i, pt) for (int i(iHead[pt]); i; i = all[i].next)//遍历属于这个点的所有边

class edge
{
public:
	int to, next, len;//len即边权
}all[1123456];

int iHead[112345];

int iEnd(2);

void add(int fr, int to, int len)
{
	all[iEnd].to = to;
	all[iEnd].len = len;
	all[iEnd].next = iHead[fr];
	iHead[fr] = iEnd++;
}

bool bColored[112345];//是否被染色
int color[112345];//染的颜色，值为0，1

int n;

inline int min(int a, int b) { return a < b ? a : b; }

int bfs(int st)
{
	int clr[2] = { 0, 0 };//第一行中被染成0，1颜色的点各有多少（计数）
	std::queue<int> que;
	que.push(st);
	bColored[st] = true;
	while (!que.empty())
	{
		int now(que.front());
		que.pop();
		if (now < n)//将点的位置限制在第一行
			++clr[color[now]];
		FOR_EDGE(i, now)
		{
			if (!bColored[all[i].to])//这个点不应该被染过色，否则就是搜索回去了
			{
				bColored[all[i].to] = true;
				color[all[i].to] = color[now] ^ all[i].len;
				que.push(all[i].to);
			}
		}
	}
	return min(clr[0], clr[1]);//返回较小值为联通块的解
}



int pos[112345];//哲学建图——pos[h]表示高度为h的士兵第一次出现的行数（为了避免初始化，行数选用1，2）
int rank[112345];//哲学建图——rank[h]表示高度为h的士兵第一次出现的编号

int main()
{
	scanf("%d", &n);
	for (int i(0); i != n; ++i)
	{
		int x;
		scanf("%d", &x);
		if (pos[x])
		{
			add(rank[x], i, 1);//读入并建图（建图这种东西……见仁见智吧）
			add(i, rank[x], 1);
		}
		else
		{
			pos[x] = 1;
			rank[x] = i;
		}
	}
	for (int i(0); i != n; ++i)
	{
		int x;
		scanf("%d", &x);
		if (pos[x])
		{
			add(rank[x], i, pos[x] == 2);//读入并建图（建图这种东西……见仁见智吧）
			add(i, rank[x], pos[x] == 2);
		}
		else
		{
			pos[x] = 2;
			rank[x] = i;
		}
	}
	for (int i(0); i != n; ++i)
	{
		add(i, n + i, 1);//隐含的建图条件：同一列的两个士兵有边且边权为1
		add(n + i, i, 1);
	}
	int ans(0);
	for (int i(0); i != n; ++i)
	{
		if (!bColored[i])//如果这个联通块内有一个点被染了色，那么整个联通块都是有色的，即已经加入答案了，就跳过
			ans += bfs(i);//答案加上这个联通块的解
	}
	printf("%d\n", ans);
	return 0;
}