CF1830E Bully Sort

On a permutation $ p $ of length $ n $ , we define a bully swap as follows: - Let $ i $ be the index of the largest element $ p_i $ such that $ p_i \neq i $ . - Let $ j $ be the index of the smallest element $ p_j $ such that $ i < j $ . - Swap $ p_i $ and $ p_j $ . We define $ f(p) $ as the number of bully swaps we need to perform until $ p $ becomes sorted. Note that if $ p $ is the identity permutation, $ f(p)=0 $ . You are given $ n $ and a permutation $ p $ of length $ n $ . You need to process the following $ q $ updates. In each update, you are given two integers $ x $ and $ y $ . You will swap $ p_x $ and $ p_y $ and then find the value of $ f(p) $ . Note that the updates are persistent. Changes made to the permutation $ p $ will apply when processing future updates.

The first line of the input contains two integers $ n $ and $ q $ ( $ 2 \le n \le 5 \cdot 10^5 $ , $ 1 \le q \le 5 \cdot 10^4 $ ) — the length of the permutation and the number of updates. The second line of input contains $ n $ integer $ p_1,p_2,\ldots,p_n $ ( $ 1 \leq p_i \leq n $ ) — the permutation $ p $ . All elements of $ p $ are distinct. The $ i $ -th of the next $ q $ lines of input contains two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i < y_i \le n $ ) — describing the $ i $ -th update.

After each update, output $ f(p) $ .

After the first update, we have $ f(p)=5 $ . The $ 5 $ bully swaps are illustrated below. - $ [\mathbf{1}, 2, \mathbf{8}, 5, 3, 4, 7, 6] $ , - $ [1, 2, \mathbf{3}, 5, \mathbf{8}, 4, 7, 6] $ , - $ [1, 2, 3, 5, \mathbf{4}, \mathbf{8}, 7, 6] $ , - $ [1, 2, 3, 5, 4, \mathbf{6}, 7, \mathbf{8}] $ , - $ [1, 2, 3, \mathbf{4}, \mathbf{5}, 6, 7, 8] $ .