CF 1131B Draw!

　　　　　　　　　　　　　　　　　　　　　　　　　Draw!

Time Limit:2000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u

 

Description

You still have partial information about the score during the historic football match. You are given a set of pairs $(ai,bi)(ai,bi),\; indicating\; that\; at\; some\; point\; during\; the\; match\; the\; score\; was\; "aiai: bibi".\; It\; is\; known\; that\; if\; the\; current\; score\; is\; «xx:yy»,\; then\; after\; the\; goal\; it\; will\; change\; to\; "x+1x+1:yy"\; or\; "xx:y+1y+1".\; What\; is\; the\; largest\; number\; of\; times\; a\; draw\; could\; appear\; on\; the\; scoreboard?$

The pairs "${\mathrm{aiai:bibi"\; are\; given\; in\; chronological\; order\; (time\; increases),\; but\; you\; are\; given\; score\; only\; for\; some\; moments\; of\; time.\; The\; last\; pair\; corresponds\; to\; the\; end\; of\; the\; match.}}^{}$

Input

The first line contains a single integer $\mathrm{nn (1\le n\le 100001\le n\le 10000)\; —\; the\; number\; of\; known\; moments\; in\; the\; match.}$

Each of the next $\mathrm{nn lines\; contains\; integers aiai and bibi (0\le ai,bi\le 1090\le ai,bi\le 109),\; denoting\; the\; score\; of\; the\; match\; at\; that\; moment\; (that\; is,\; the\; number\; of\; goals\; by\; the\; first\; team\; and\; the\; number\; of\; goals\; by\; the\; second\; team).}$

All moments are given in chronological order, that is, sequences ${\mathrm{xixi and yjyj are\; non-decreasing.\; The\; last\; score\; denotes\; the\; final\; result\; of\; the\; match.}}^{}$

Output

Print the maximum number of moments of time, during which the score was a draw. The starting moment of the match (with a score 0:0) is also counted.

Sample Input

Input

3
2 0
3 1
3 4

Output

2

Input

3
0 0
0 0
0 0

Output

1

Input

1
5 4

Output

5

Hint

In the example one of the possible score sequences leading to the maximum number of draws is as follows: 0:0, 1:0, 2:0, 2:1, 3:1, 3:2, 3:3, 3:4.

 题意:

两个人进行比赛，给出几场两人的比分,问在满足这几场比分的条件下，最多会出现几场平局(开始的0:0也算一场）。

 解题思路：

将比赛双方看成两条不断前进的线段，利用区间的方式去模拟比赛的情况。

 重点是Debug，在思路找不到错误的情况下，就去多试一些样例，尽量的做到测试的不重不漏。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<iostream>
using namespace std;
typedef long long  LL;
const double pi=acos(-1.0);
const double e=exp(1);
const int N = 100009;


queue<LL> check;
int main()
{
    LL i,p,j,n,t;
    LL ans = 0;
    LL a1,b1,a2,b2;

    while(!check.empty())
        check.pop();

    scanf("%lld",&n);
    scanf("%lld%lld",&a1,&b1);

    ans += min(a1, b1) + 1;
    check.push(min(a1,b1));
    for(i = 1; i < n; i ++)
    {
        scanf("%lld%lld",&a2,&b2);
        if(a2 < b1 || a1 > b2)
            ;
        else if(a1 < b1 && a2 <= b2 && a2 >= b1)
        {
            ans+=(a2 - b1) + 1;


            if(check.front() == b1)
            {
                ans--;

            }
            check.pop();
            check.push(a2);
        }
        else if(a1 >= b1 && a2 <= b2)
        {
            ans+=(a2 - a1 + 1);

            if(check.front() == a1)
            {
                ans--;

            }
            check.pop();
            check.push(a2);
        }
        else if(a1 >= b1 && a1 <= b2 && a2 > b2)
        {
            ans += b2 - a1 + 1;

            if(check.front() == a1)
            {
                ans--;

            }
            check.pop();
            check.push(b2);
        }
        else if(a1 <= b1 && a2 >= b2)
        {
            ans += b2 - b1 + 1;

            if(check.front() == b1)
            {
                ans--;

            }
            check.pop();
            check.push(b2);
        }
        a1 = a2;
        b1 = b2;
    }
    printf("%lld
",ans);
    return 0;
}