Public Judge

pjudge

Time Limit: 2 s Memory Limit: 256 MB Total points: 100 Hackable ✓
Statistics

题目描述

今天是 YQH 的生日,她得到了一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$ 作为生日礼物。

然而,YQH 并不对这个序列满意,因为这个序列可能并不合法。

一个序列 $\{a_i\}$ 合法,当且仅当 $\max\limits_{i=1}^n\{a_i\}+\min\limits_{i=1}^n\{a_i\}>n$,其中 $n$ 为序列长度,特别的,我们规定 $\varnothing$ 是合法的。

为了让 YQH 满意,你需要找到一个 $a_1,a_2,\dots,a_n$ 的一个子段,使得这个子段是合法的。一个序列 $b_1,b_2,\dots,b_m$ 是 $a_1,a_2,\dots,a_n$ 的子段当且仅当 $b_1,b_2,\dots,b_m$ 可以由 $a_1,a_2,\dots,a_n$ 删掉若干个(可以为 $0$)开头及结尾的元素得到,比如 $[2,3],[1,2],[3,4],[1,2,3,4],\varnothing$ 都是 $[1,2,3,4]$ 的子段。

符合条件的子段可能很多,所以 YQH 只想要你找到,$a_1,a_2,\dots,a_n$ 的所有合法子段的长度的最大值。

然而,YQH 得到的序列有魔力,所以它会产生变化,YQH 希望你对于初始的以及每次变化后的 $\{a_i\}$ 都求出答案。

输入格式

第一行一个正整数及一个非负整数 $n,m$。其中 $m$ 是 $\{a_i\}$ 的变化次数。

第二行 $n$ 个整数表示初始的 $a_1,a_2,\dots,a_n$。

接下来,描述 $m$ 次变化,每次变化由若干行描述:

其中第一行一个非负整数表示 $k$,接下来 $k$ 行,第 $i$ 行两个正整数 $x_i,y_i$。假如变化前的序列为 $\{a_i\}$,那么对 $\{a_i\}$ 依次交换 $(a_{x_1},a_{y_1}),(a_{x_2},a_{y_2}),\dots,(a_{x_k},a_{y_k})$,得到的序列 $\{a^\prime_i\}$ 就是变化后的序列。

变化之间不独立(见样例解释)

输出格式

第一行一个整数表示初始 $\{a_i\}$ 的答案。

接下来 $m$ 行,第 $i$ 行一个整数表示第 $i$ 次变化后的答案。

样例

输入1

5 2
1 2 -2 3 4
1
2 3
1
1 2

输出1

2
3
4

$\{a_i\}$ 初始为 $[1,2,-2,3,4]$,其中一个合法子段为 $[3,4]$。

第一次变化,交换 $(a_2,a_3)$ 后 $\{a_i\}$ 为 $[1,-2,2,3,4]$,其中一个合法子段为 $[2,3,4]$。

第二次变化,交换 $(a_1,a_2)$,$\{a_i\}$ 为 $[-2,1,2,3,4]$,其中一个合法子段为 $[1,2,3,4]$。

输入2

5 2
-1 -1 2 1 1
2
3 4
2 5
2
2 5
1 4

输出2

2
2
1

$\{a_i\}$ 初始为 $[-1,-1,2,1,1]$,其中一个合法子段为 $[2,1]$。

第一次变化,先交换 $(a_3,a_4)$,再交换 $(a_2,a_5)$,最终 $\{a_i\}$ 为 $[1,1,1,2,-1]$,其中一个合法子段为 $[1,2]$。

第二次变化,先交换 $(a_2,a_5)$,再交换 $(a_1,a_4)$,最终 $\{a_i\}$ 为 $[2,-1,1,1,1]$,其中一个合法子段为 $[1]$。

样例输入/输出 3

见下发文件中的 ex_loose3.in/ex_loose3.ans

样例输入/输出 4

见下发文件中的 ex_loose4.in/ex_loose4.ans

数据范围

令所有变化的交换次数 $k$ 之和为 $K$。

对于所有数据,保证 $1\le n\le 10^6,0\le m\le 30,0\le K\le 10^6,|a_i|\le 10^9,x_i\ne y_i$。

子任务编号 $n\le$ $m\le$ 分值
$1$ $2000$ $30$ $20$
$2$ $2\times10^5$ $2$ $20$
$3$ $10^6$ $2$ $20$
$4$ $10^6$ $30$ $40$