思路及代码参考：

There is an infinite sequence consisting of all positive integers in the increasing order: p = {1, 2, 3, ...}. We performed n swap operations with this sequence. A swap(a, b) is an operation of swapping the elements of the sequence on positions aand b. Your task is to find the number of inversions in the resulting sequence, i.e. the number of such index pairs (i, j), that i < j and p_i > p_j.

Input

The first line contains a single integer n (1 ≤ n ≤ 10⁵) — the number of swapoperations applied to the sequence.

Each of the next n lines contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ 10⁹, a_i ≠ b_i) — the arguments of the swap operation.

Output

Print a single integer — the number of inversions in the resulting sequence.

Examples

Input

2 4 2 1 4

Output

4

Input

3 1 6 3 4 2 5

Output

15

Note

In the first sample the sequence is being modified as follows: . It has 4 inversions formed by index pairs (1, 4), (2, 3), (2, 4) and (3, 4).

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              const int maxn=2e5+5;typedef long long ll;using namespace std;ll s[maxn],sum[maxn];int ss[maxn];int a[maxn],b[maxn],pos[maxn];int lowbit(int x){ return x&(-x);}int n;void update(int pos,int ad){ while(pos<=maxn) { s[pos]+=ad; pos+=lowbit(pos); }}ll getnum(int pos){ ll res=0; while(pos>0) { res+=s[pos]; pos-=lowbit(pos); } return res;}int main(){ int n; while (~scanf("%d", &n)) { for (int i = 1; i <= n; i++) { scanf("%d%d", &a[i], &b[i]); ss[i] = a[i]; ss[i + n] = b[i]; pos[i] = i; pos[i + n] = i + n; } sort(ss + 1, ss + 2 * n + 1); ss[0] = 0; int cnt = 0; for (int i = 1; i <= 2 * n;i++) if (i == 1 || ss[i] != ss[i - 1]) ss[++cnt] = ss[i]; sum[0] = 0; for (int i = 1; i <= cnt; i++) sum[i] = sum[i - 1] + ss[i] - ss[i - 1] - 1; for (int i = 1; i <= n; i++) { int aa = lower_bound(ss + 1, ss + cnt + 1, a[i]) - ss; int bb = lower_bound(ss + 1,ss + cnt + 1, b[i]) - ss; swap(pos[aa], pos[bb]); } memset(s, 0, sizeof(s)); ll ans = 0; for (int i = cnt; i; i--) { ans += getnum(pos[i]); ans += abs(sum[i]-sum[pos[i]]); update(pos[i], 1); } printf("%lld\n", ans); } return 0;}