B"It turns out that this is exactly the 100 -th problem of mine that appears in some programming competition. So it has to be special! And what can be more special than another problem about LIS... You are given a permutation p_1, p_2, ldots, p_{2n+1} of integers from 1 to 2n+1 . You will have to process q updates, where the i -th update consists in swapping p_{u_i}, p_{v_i} . After each update, find any cyclic shift of p with LIS <= n , or determine that there is no such shift. (Refer to the output section for details). Here LIS(a) denotes the length of longest strictly increasing subsequence of a . Hacks are disabled in this problem. Don't ask why. The first line of the input contains two integers n, q ( 2 <= n <= 10^5 , 1 <= q <= 10^5 ). The second line of the input contains 2n+1 integers p_1, p_2, ldots, p_{2n+1} ( 1 <= p_i <= 2n+1 , all p_i are distinct) -- the elements of p . The i -th of the next q lines contains two integers u_i, v_i ( 1 <= u_i, v_i <= 2n+1 , u_i neq v_i ) -- indicating that you have to swap elements p_{u_i}, p_{v_i} in the i -th update. After each update, output any k (0 <= k <= 2n) , such that the length of the longest increasing subsequence of (p_{k+1}, p_{k+2}, ldots, p_{2n+1}, p_1, ldots, p_k) doesn't exceed n , or -1 , if there is no such k . After the first update, our permutation becomes (5, 2, 3, 4, 1) . We can show that all its cyclic shifts have LIS ge 3 . After the second update, our permutation becomes (1, 2, 3, 4, 5) . We can show that all its cyclic shifts have LIS ge 3 . After the third update, our permutation becomes (1, 2, 3, 5, 4) . Its shift by 2 is (3, 5, 4, 1, 2) , and its LIS = 2 . After the fourth update, our permutation becomes (1, 2, 3, 4, 5) . We can show that all its cy"...