Processing math: 100%
Hotspot - MarisaOJ: Marisa Online Judge

Hotspot

Time limit: 1000 ms
Memory limit: 512 MB
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