题目描述

每个题目都要有名字，不知道怎么取名也要有名字。——《鲁迅说的》
给定长度为 $n$ 的一个排列 $p_1 \sim p_n$，定义 $a_i$ 为满足 $j<i$ 且 $p_j<p_i$ 的 $j$ 的个数；$b_i$ 为满足 $j>i$ 且 $p_j<p_i$ 的 $j$ 的个数，$c_i=\min(a_i,b_i)$。
然后有 $q$ 次查询，每一次输入 $x,y$，请你回答如果交换 $p_x,p_y$，$\sum_{i=1}^n c_i$ 是多少。
ps: 每次交换只会影响当前查询。

输入格式

第一行两个整数 $n,q$。
第二行 $n$ 个整数 $p_1 \sim p_n$，保证是一个排列。 接下来 $q$ 行，每行两个整数 $x,y$。

输出格式

共 $q$ 行，每行一个整数，对应当前询问的答案。

样例输入1

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

样例输出1

7
6
6
7
7
6
8

数据范围

对于 30% 的数据 $n,q\le 2000$； 对于另外 20% 的数据 保证 $y-x\le 100$。 对于 100% 的数据，保证 $n,q\le 500000,1\le x\le y\le n$。