시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 10 | 5 | 4 | 50.000% |
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.
5 2 1 2 -2 3 4 1 2 3 1 1 2
2 3 4