给定一个大小为 $n$ 的排列 $p_1, p_2, \dots, p_n$。计算以下值： $$f(p) = \min_{i \neq j} |i - j| \cdot |p_i - p_j|$$

同时给定 $q$ 次查询。第 $i$ 次查询包含两个下标 $a_i$ 和 $b_i$。你需要交换这些位置上的元素（交换 $p_{a_i}$ 和 $p_{b_i}$），然后重新计算 $f(p)$ 的值。注意，这些修改在查询之间是持久的：在第 $i$ 次查询后，总共进行了 $i$ 次交换。

大小为 $n$ 的排列是指一个包含 $1$ 到 $n$ 这 $n$ 个不同整数的序列。

输入格式

第一行包含两个整数：排列的大小 $n$ ($2 \le n \le 10^5$) 和查询次数 $q$ ($1 \le q \le 10^5$)。

第二行描述排列 $p$。

接下来的 $q$ 行，每行描述一个查询。第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n; a_i \neq b_i$)，表示需要交换的元素下标。

输出格式

输出 $q + 1$ 行：初始状态下 $f(p)$ 的值，以及每次查询后 $f(p)$ 的值。

样例

样例输入 1

6 5
2 4 1 6 3 5
1 2
3 5
1 2
5 3
5 6

样例输出 1

2
1
1
1
2
1