Description
Statements
A university in Samara has held a qualification contest in figure programming, but the jury can't come to terms how many teams should take part in the next stage of the contest. In figure programming a judge system doesn't evaluate the scores precisely and just set an interval which the score can belong to. Jury is able to evaluate any participant with any score from this interval. There are n teams that took part in the contest, and the i-th of them has the score in the interval from li to ri, inclusively. Jury wants the number of qualified teams to be as large as possible, but they have to get the maximal score among all teams. What is the maximal number of teams that can take part in the next stage of the contest under such circumstances?
Input
The first line contains a single integer n (1 ≤ n ≤ 2·105) — the number of teams in the contest.
Each of the next n lines contains two space-separated integers: li and ri ( - 109 ≤ li ≤ ri ≤ + 109) — the lower and upper bounds of the score for the i-th team.
Output
Output a single integer — the maximal number of teams that can get the maximal score.
Sample Input
3 1 3 2 4 4 5
2
先求左端最大，然后求有几个超过右端的数。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define mod 1000000007
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
ll n,a[200005],t,re = 0;
int main()
{
memset(a,0,sizeof(a));
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
re += a[1];
for(int i=2;i<=n;i++)
{
if(a[i]>a[i-1])
{
re += a[i]-a[i-1];
}
}
cout << re <<endl;
return 0;
}