Chef and Swaps

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
This time, Chef has given you an array A containing N elements.
He had also asked you to answer M of his questions. Each question sounds like: "How many inversions will the array A contain, if we swap the elements at the ith and the jth positions?".
The inversion is such a pair of integers (i, j) that i < j and A_{i} > A_{j}.
Input
The first line contains two integers N and M  the number of integers in the array A and the number of questions respectively.
The second line contains N spaceseparated integers  A_{1}, A_{2}, ..., A_{N}, respectively.
Each of next M lines describes a question by two integers i and j  the 1based indices of the numbers we'd like to swap in this question.
Output
Output M lines. Output the answer to the ith question of the ith line.
Constraints
 1 ≤ N, M ≤ 2 * 10^{5}
 1 ≤ i, j ≤ N
 1 ≤ A_{i} ≤ 10^{9}
 Mind that we don't actually swap the elements, we only answer "what if" questions, so the array doesn't change after the question.
Example
Input: 6 3 1 4 3 3 2 5 1 1 1 3 2 5 Output: 5 6 0
Explanation
Inversions for the first case: (2, 3), (2, 4), (2, 5), (3, 5), (4, 5).
Inversions for the second case: (1, 3), (1, 5), (2, 3), (2, 4), (2,5), (4, 5).
In the third case the array looks like 1 2 3 3 4 5 and there are no inversions.
Author:  berezin 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/CHEFINV 
Tags  berezin, fenwick, inversions, medium, sept14 
Date Added:  24032014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 