Anton likes permutations, especially he likes to permute their elements. Note that a permutation of *n* elements is a sequence of numbers {*a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>}, in which every number from 1 to *n* appears exactly once.

One day Anton got a new permutation and started to play with it. He does the following operation *q* times: he takes two elements of the permutation and swaps these elements. After each operation he asks his friend Vanya, how many inversions there are in the new permutation. The number of inversions in a permutation is the number of distinct pairs (*i*, *j*) such that 1 ≤ *i* &lt; *j* ≤ *n* and *a*<sub class="lower-index">*i*</sub> &gt; *a*<sub class="lower-index">*j*</sub>.

Vanya is tired of answering Anton's silly questions. So he asked you to write a program that would answer these questions instead of him.

Initially Anton's permutation was {1, 2, ..., *n*}, that is *a*<sub class="lower-index">*i*</sub> = *i* for all *i* such that 1 ≤ *i* ≤ *n*.
The first line of the input contains two integers *n* and *q* (1 ≤ *n* ≤ 200 000, 1 ≤ *q* ≤ 50 000) — the length of the permutation and the number of operations that Anton does.

Each of the following *q* lines of the input contains two integers *l*<sub class="lower-index">*i*</sub> and *r*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> ≤ *n*) — the indices of elements that Anton swaps during the *i*-th operation. Note that indices of elements that Anton swaps during the *i*-th operation can coincide. Elements in the permutation are numbered starting with one.
Consider the first sample.

After the first Anton's operation the permutation will be {1, 2, 3, 5, 4}. There is only one inversion in it: (4, 5).

After the second Anton's operation the permutation will be {1, 5, 3, 2, 4}. There are four inversions: (2, 3), (2, 4), (2, 5) and (3, 4).

After the third Anton's operation the permutation will be {1, 4, 3, 2, 5}. There are three inversions: (2, 3), (2, 4) and (3, 4).

After the fourth Anton's operation the permutation doesn't change, so there are still three inversions.
5 4
4 5
2 4
2 5
2 2
1
4
3
3
2 1
2 1
1
6 7
1 4
3 5
2 3
3 3
3 6
2 1
5 1
5
6
7
7
10
11
8
42 42
23 7
9 6
17 22
19 23
15 42
14 10
17 12
2 25
8 39
13 9
29 26
17 2
11 14
33 20
29 1
4 28
25 4
37 32
6 37
30 42
39 1
12 29
39 3
6 41
26 34
11 21
21 32
20 35
6 22
32 35
34 40
33 14
13 10
1 2
5 12
21 9
41 30
5 27
29 35
22 32
1 1
2 10
31
34
43
40
91
98
103
146
199
202
207
196
195
214
257
294
259
266
305
302
267
248
289
306
309
316
335
338
323
328
333
342
341
342
341
356
361
390
387
384
384
383
1 1
1 1
0
200000 2
42 199685
65536 65536
399285
399285
200000 1
92734 60628
64211
50000 6
15501 15522
25641 25642
37466 37572
37500 37502
49148 49222
9584 9585
41
42
253
256
403
404
while True:
    n,q=map(int,input().split(" "))
    nums=[i for i in range(1,n+1)]
    q_mani=[]
    for qi in range(q):
        q_mani.append(list(map(int,input().split(" "))))
    #print(nums)
    nums_len=len(nums)
    cnt=0
    for qi in range(q):
        
        x=q_mani[qi][0]-1
        y=q_mani[qi][1]-1
        
        if x>y:
            x,y=y,x
        if nums[x]<nums[y]:
          cnt+=1
        if nums[x]>nums[y]:
          cnt-=1
        for i in range(x+1,y):
            if nums[i]>nums[x]:
                cnt+=1
            if nums[i]<nums[x]:
                cnt-=1
            if nums[i]>nums[y]:
                cnt-=1
            if nums[i]<nums[y]:
                cnt+=1
        nums[x],nums[y]=nums[y],nums[x]

        print(f"{cnt}")