题目描述

Robert 创建了一道线段树题，题目是：

给定长为 $N$ 的排列 $a_i$，我们规定一个翻牌操作为将一个区间的最小值与最大值交换。现在给定您 $Q$ 个翻牌操作，每次对 $[l,r]$ 执行翻牌操作，求进行 $Q$ 次翻牌操作后的最终序列。

搞好了题目描述，接下来要搞数据了。

现在给定了 $N$，初始序列 $a_i$ 和最终序列，求中间要进行的翻牌操作。

输入格式

第一行一个整数代表序列长度 $N$。
第二行 $N$ 个整数代表初始序列 $a_i$。
第三行 $N$ 个整数代表最终序列。

输出格式

首先第一行一个整数 $Q$ 代表要进行的翻牌操作的次数。
接下来 $Q$ 行每行两个整数 $l,r$ 代表对 $[l,r]$ 进行翻牌操作。

6
1 3 5 6 4 2
1 2 3 4 5 6

4
2 3
3 6
2 5
4 5

提示

样例说明

对于样例 $1$，执行的 $4$ 次翻牌操作为：

• 对 $[2,3]$ 进行翻牌操作，交换 $3$ 和 $5$
• 对 $[3,6]$ 进行翻牌操作，交换 $6$ 和 $2$
• 对 $[2,5]$ 进行翻牌操作，交换 $5$ 和 $2$
• 对 $[4,5]$ 进行翻牌操作，交换 $5$ 和 $4$

数据规模与约定

对于 $100\%$ 的数据，$1 \le a_i \le N \le 4096$，$1 \le Q \le 3 \times 10^5$，$1 \le l\le r \le N$。
对于其中 $20\%$ 的数据，$N \le 100$。
对于另外 $40\%$ 的数据，$N \le 2048$。

说明

翻译自 Canadian Computing Olympiad 2018 Day 2 C Flop Shorting。