21076번 - Longest Loose Segment 다국어

문제

A list $A$ is called loose if $\max(A) + \min(A) > \text{len}(A)$.

Today Rikka got a list $A$ of length $n$. She wants to find the longest segment $[l, r]$ in $A$ such that list $[A_l, A_{l + 1}, \ldots, A_r]$ is loose.

Rikka will make $m$ turns with list $A$. On each turn, Rikka will perform one or more given operations in sequence. Each operation is swapping two elements in list $A$. Your task is to calculate the length of the longest loose segment of $A$ and the resulting list after each turn.

Note that the operations on turn $i$ are performed on the list that was the result of turn $(i - 1)$.

입력

The first line contains two integers $n$ and $m$ (1ドル \leq n \leq 10^6$ and 1ドル \leq m \leq 30$).

The second line contains $n$ integers $A_i$ ($-10^6 \leq A_i \leq 10^6$) that constitute the initial list $A$.

Then follow $m$ descriptions of the turns. For each turn, the first line contains a single integer $k$ (1ドル \leq k \leq 10^6$), the number of swaps. Then $k$ lines follow: each of them contains two integers $u_i$ and $v_i$ (1ドル \leq u_i, v_i \leq n$ and $u_i \neq v_i$) such that Rikka will swap $A_{u_i}$ and $A_{v_i}$ in this operation.

It is guaranteed that $\sum k \leq 10^6$.

출력

On the first line, output a single integer: the length of the longest loose segment of $A$.

Then output $m$ lines. On each of them, print a single integer: the length of the longest loose segment of the resulting list after each turn.

제한

힌트