【UER #13】拆弹专家
你是跳蚤国知名的拆弹专家。已知地雷上的加密装置是一个长度为 $n$ 的数组 $a$，地雷将在 $T$ 秒后进入不可逆的引爆程序。信息中心刚刚从敌方频道截获了两条关键信息：
一个长度为 $n$ 的数组 $b$，表示地雷密钥，当 $a=b$ 时地雷解除。
$T$ 个操作窗口 $(l_1,r_1),(l_2,r_2)...(l_T,r_T)$。在第 $i$ 秒时，你可以任意重排 $a$ 数组下标在 $[l_i,r_i]$ 中的数字。
战机紧迫，刻不容缓！信息中心希望你能尽快拆除地雷，你需要计算出最早什么时候可以拆除，或者汇报无法拆除。
输入格式
一行两个正整数 $n, T$。
接下来两行，每行 $n$ 个整数。分别表示 $a,b$ 数组。
接下来 $T$ 行，每行两个整数，表示 $l_i,r_i$。
输出格式
输出一个 $[0,T+1]$ 中的整数，表示最早什么时候可以拆除。
若无需任何操作，输出 $0$；若炸弹无法拆除，输出 $T+1$。
5 3
1 1 2 2 1
2 1 2 1 1
1 3
3 4
1 2
2
5 1
1 1 2 2 1
1 1 2 2 1
1 3
0
5 4
1 1 1 1 2
2 1 1 1 1
1 2
3 4
1 2
3 5
5
5 1
3 4 5 1 2
1 2 3 4 5
1 5
1
样例五 $\sim$ 十一
见“附件下载”，这部分样例，样例 $i$ 满足子任务 $i-4$ 的约束。
数据范围
对于所有数据，保证 $1 \leq n\leq 10^4,1\le T\le 2\times 10^6, 1 \leq l_i \leq r_i \leq n, 1\le a_i,b_i\le n$，保证 $a,b$ 数组每种数字出现次数相同。
| 子任务编号 | $n\leq $ | $T\le $ | 特殊性质 | 分值 |
|---|---|---|---|---|
| $1$ | $10$ | $10$ | 无 | $5$ |
| $2$ | $500$ | $500$ | 无 | $10$ |
| $3$ | $10^4$ | $10^4$ | $a,b$ 均为排列 | $10$ |
| $4$ | $10^4$ | $10^4$ | 无 | $15$ |
| $5$ | $2000$ | $2\times 10^6$ | $a,b$ 均为排列 | $15$ |
| $6$ | $2000$ | $2\times 10^6$ | 无 | $20$ |
| $7$ | $10^4$ | $2\times 10^6$ | 无 | $25$ |
时间限制：$\texttt{1s}$
空间限制：$\texttt{512MB}$