Permutation and Queries

You are given a permutation $p_1, p_2, \ldots, p_n$ of size $n$. Calculate the value $$f(p) = \min\limits_{i \neq j} |i - j| \cdot |p_i - p_j|\text{.}$$ 

You are also given $q$ queries. The $i$-th query consists of two indices $a_i$ and $b_i$. You should swap the elements at these positions (swap $p_{a_i}$ and $p_{b_i}$), and then recalculate the value $f(p)$. Note that the changes persist between queries: after $i$-th query, there are $i$ swaps made.

A permutation of size $n$ is a sequence of $n$ distinct integers from $1$ to $n$.

The first line contains two integers: the permutation size $n$ ($2 \le n \le 10^5$) and the number of queries $q$ ($1 \le q \le 10^5$).

The second line describes the permutation $p$.

Each of the next $q$ lines describes a query. The $i$-th of these lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$; $a_i \ne b_i$): the indices of elements you should swap.

Print $q + 1$ lines: the value $f(p)$ before all queries and after each of the $q$ queries.