题目描述

译自 Canadian Computing Olympiad 2018 Day 2 C Flop Sorting

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

给定一个 $1$ 到 $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

数据范围与提示

对于 $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$。