题目描述
今天是 YQH 的生日,她得到了一个长度为 n 的整数序列 a1,a2,…,an 作为生日礼物。
然而,YQH 并不对这个序列满意,因为这个序列可能并不合法。
一个序列 {ai} 合法,当且仅当 nmaxi=1{ai}+nmini=1{ai}>n,其中 n 为序列长度,特别的,我们规定 ∅ 是合法的。
为了让 YQH 满意,你需要找到一个 a1,a2,…,an 的一个子段,使得这个子段是合法的。一个序列 b1,b2,…,bm 是 a1,a2,…,an 的子段当且仅当 b1,b2,…,bm 可以由 a1,a2,…,an 删掉若干个(可以为 0)开头及结尾的元素得到,比如 [2,3],[1,2],[3,4],[1,2,3,4],∅ 都是 [1,2,3,4] 的子段。
符合条件的子段可能很多,所以 YQH 只想要你找到,a1,a2,…,an 的所有合法子段的长度的最大值。
然而,YQH 得到的序列有魔力,所以它会产生变化,YQH 希望你对于初始的以及每次变化后的 {ai} 都求出答案。
输入格式
第一行一个正整数及一个非负整数 n,m。其中 m 是 {ai} 的变化次数。
第二行 n 个整数表示初始的 a1,a2,…,an。
接下来,描述 m 次变化,每次变化由若干行描述:
其中第一行一个非负整数表示 k,接下来 k 行,第 i 行两个正整数 xi,yi。假如变化前的序列为 {ai},那么对 {ai} 依次交换 (ax1,ay1),(ax2,ay2),…,(axk,ayk),得到的序列 {a′i} 就是变化后的序列。
变化之间不独立(见样例解释)
输出格式
第一行一个整数表示初始 {ai} 的答案。
接下来 m 行,第 i 行一个整数表示第 i 次变化后的答案。
样例
输入1
5 2 1 2 -2 3 4 1 2 3 1 1 2
输出1
2 3 4
{ai} 初始为 [1,2,−2,3,4],其中一个合法子段为 [3,4]。
第一次变化,交换 (a2,a3) 后 {ai} 为 [1,−2,2,3,4],其中一个合法子段为 [2,3,4]。
第二次变化,交换 (a1,a2),{ai} 为 [−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
{ai} 初始为 [−1,−1,2,1,1],其中一个合法子段为 [2,1]。
第一次变化,先交换 (a3,a4),再交换 (a2,a5),最终 {ai} 为 [1,1,1,2,−1],其中一个合法子段为 [1,2]。
第二次变化,先交换 (a2,a5),再交换 (a1,a4),最终 {ai} 为 [2,−1,1,1,1],其中一个合法子段为 [1]。
样例输入/输出 3
见下发文件中的 ex_loose3.in/ex_loose3.ans
。
样例输入/输出 4
见下发文件中的 ex_loose4.in/ex_loose4.ans
。
数据范围
令所有变化的交换次数 k 之和为 K。
对于所有数据,保证 1≤n≤106,0≤m≤30,0≤K≤106,|ai|≤109,xi≠yi。
子任务编号 | n≤ | m≤ | 分值 |
---|---|---|---|
1 | 2000 | 30 | 20 |
2 | 2×105 | 2 | 20 |
3 | 106 | 2 | 20 |
4 | 106 | 30 | 40 |