题目描述

给你一个长度为 $n$ 的排列 $a_1,a_2, \cdots ,a_n$。

若要将区间 $[l,r]$ 升序排序，需要花 $(r-l+1)^2$ 的代价，因为你只会冒泡排序。

你需要操作一次把它升序排序，求最小代价。

为了确定你真的会这个题，数据用了一些神秘变换来变换这个序列。

有 $q$ 次变换，每次变换给定 $x,y$，然后交换 $a_x,a_y$。

每次变换会互相影响，且每次变换后你需要输出当前的最小代价。

输入格式

输入共 $q+2$ 行。

第一行两个数 $n,q$，意义如题目描述所述。

第二行 $n$ 个数，第 $i$ 个数表示初始的 $a_i$。

以下 $q$ 行，每行两个数 $x',y'$。

设 $\text{lastans}$ 表示上一次询问的答案，如果之前没有询问，$\text{lastans}=0$。

每次询问你需要交换 $a_{(x'-1+\text{lastans}) \bmod n + 1},a_{(y'-1+\text{lastans}) \bmod n +1}$。

输出格式

输出共 $q$ 行。

对于每次询问，输出一行一个数表示答案。

3 1
3 2 1
1 2

9

提示

样例解释

序列是 $[2,3,1]$，排序一次整个序列可以消耗 $9$ 的代价。

可以证明这是最小代价。

数据范围

对于所有数据，$1 \leq n,q \leq 5000,1 \leq a_i,x',y' \leq n$，保证 $a_i$ 互不相同。