P17041 [NWERC 2021] 交换学生 / Exchange Students

译自 [Northwestern Europe Regional Contest (NWERC) 2021](http://2021.nwerc.eu) Problem E。 原题许可协议为 CC BY-SA。

Reykjavik University 的一组 $n$ 名交换学生正在排队拍集体照。从左到右，学生们的身高为 $g_1,g_2,\ldots,g_n$。然而，摄影师希望重新排列学生，使他们的身高顺序变为 $h_1,h_2,\ldots,h_n$。为此，摄影师会反复交换两名交换学生的位置。只有当两名学生能够看见彼此时，才能交换他们；也就是说，位于他们之间的每名学生的身高都必须严格小于这两名要交换的学生。 请确定为了将学生排列成摄影师偏好的顺序，所需的最少交换次数，并给出一个长度最小的交换序列。摄影师最多只有时间进行 $2\cdot 10^5$ 次交换。如果需要的交换次数更多，你只需要确定前 $2\cdot 10^5$ 次交换。

输入包含： - 一行一个整数 $n$（$1 \leq n \leq 3\cdot 10^5$），表示学生数量。 - 一行 $n$ 个整数 $g_1,g_2,\ldots,g_n$（$1 \leq g_i \leq 10^9$），表示学生们当前的身高顺序。 - 一行 $n$ 个整数 $h_1,h_2,\ldots,h_n$（$1 \leq h_i \leq 10^9$），表示摄影师偏好的身高顺序。 保证 $(h_1,\ldots,h_n)$ 是 $(g_1,\ldots,g_n)$ 的一个排列。

首先输出一个整数 $s$，表示所需的最少交换次数。 然后输出 $\min(s,2\cdot 10^5)$ 次交换，每次交换由两个整数 $i$ 和 $j$ 组成，表示这一步中必须交换的一基下标位置。 如果存在多个合法解，可以输出任意一个。

【数据规模与约定】 对于所有数据，$1 \leq n \leq 3\cdot 10^5$；$1 \leq g_i,h_i \leq 10^9$；$(h_1,\ldots,h_n)$ 是 $(g_1,\ldots,g_n)$ 的一个排列；最多需要输出前 $2\cdot 10^5$ 次交换。