Minimum Cost to Sort a Permutation Segment After Swap Operations

Given a permutation \(a_1,a_2,\dots,a_n\) of length \(n\), you are allowed to perform exactly one sorting operation on a contiguous subarray. Sorting the subarray \([l,r]\) in ascending order costs \((r-l+1)^2\) (since you only know bubble sort). After the operation, the entire permutation must be sorted in increasing order; that is, for all \(1 \le i \le n\), the final array satisfies \(a_i=i\).

However, before performing the sorting operation, the permutation undergoes \(q\) transformation queries. In each query, you are given two indices \(x\) and \(y\), and you swap \(a_x\) with \(a_y\). These swaps are persistent, meaning that each query affects subsequent ones. After each swap, you need to determine and output the minimum cost required to make the permutation sorted by performing a single sorting operation.

Note: To achieve a sorted permutation after sorting a subarray \([l,r]\), all elements outside the interval must already be in their correct positions (i.e. \(a_i=i\) for \(ir\)), and the subarray \(a_l,\dots,a_r\) must be a permutation of \(l,l+1,\dots,r\). Thus, if there exists any index \(i\) for which \(a_i \neq i\), let \(l\) be the smallest such index and \(r\) be the largest. The minimum cost is \((r-l+1)^2\). If the permutation is already sorted, you still must perform one operation; in that case, choose an interval of length 1 for a cost of 1.

inputFormat

The first line contains two integers \(n\) and \(q\) --- the size of the permutation and the number of queries.

The second line contains \(n\) integers --- the permutation \(a_1, a_2, \dots, a_n\).

Each of the next \(q\) lines contains two integers \(x\) and \(y\) (1-indexed) representing a swap between \(a_x\) and \(a_y\).

outputFormat

For each query, output one integer --- the minimum cost needed to sort the current permutation with one sorting operation.

sample

4 3
1 3 2 4
2 3
1 4
2 3

1
16
16