Hakurei Shrine is broke. Now Reimu has to ask Patchouli for hotspot to read doujins (God knows of what type)!
Patchouli gives Reimu a permutation of length $n$, initially sorted ascending, and $q$ queries. Each query Patchouli swaps $2$ arbitrary number, and asks Reimu: how many pairs $(i, j)$ ($1 \le i < j \le n$) satisfy the condition: For every index $k$ within the subarray from $1$ to $i$ and the subarray from $j$ to $n$, $P_k=k$?
Unfortunately, Reimu never attended Cirno's perfect math class (Marisa did for accounting but they are having a cold war ToT), so she's not very good at math. Please help her answer Patchouli's questions (so that she can use her hotspot (for doujins))!
### Input
- The first line consists of 2 integers $n, q$ - the length of the permutation, and the number of queries, respectively.
- Each of the next $q$ lines consists of 2 integers $i, j$, the indices for each query. Each number will be swapped at most $1$ time.
### Output
Print $q$ lines, the answers for the $q$ queries.
### Constraints
- $2 \le n \le 10^6$.
- $1 \le q \le$ when-Patchouli-gives-up.
### Example:
Input:
```
7 2
2 4
6 3
```
Output:
```
3
1
```
