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≤i<j≤n) satisfy the condition: For every index k within the subarray from 1 to i and the subarray from j to n, Pk=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≤n≤106.
- 1≤q≤ when-Patchouli-gives-up.
### Example:
Input:
722463
Output:
31