公元2222年，l国发生了一场战争。
小Y负责领导工人运输物资。
其中有m种物资的运输方案，每种运输方案形如li,ri。表示存在一种货物从li运到ri。
这里有n个城市，第i个城市与第i+1个城市相连（这里1号城市和n号城市并不相连），并且从i号城市走到i+1号或者从i+1号走到i号需要耗费1点时间。
由于高科技的存在，小Y想到了一种节省时间的好方案。在X号城市与Y号城市之间设立传送站，只要这么做，在X号城市走到Y号城市不需要耗费时间，同样的，从Y号城市走到X号城市也不需要耗费时间。
但是为了防止混乱，只能设立这么一条传送站。
现在这些运输方案同时进行，小Y想让最后到达目的地的运输方案时间最短。
在样例中，存在两条运输方案，分别是1号城市到3号与2号到4号，那么我们在2号城市与3号城市建立传送站，这样运输方案时间最长的只需要1点时间就可以了。
Input第一行两个整数n,m(1<=n,m<=500000)。
接下来m行，每行两个整数li,ri(1<=li,ri<=n)。（若li=ri，则不需要耗费任何时间）Output一个数表示答案。Sample Input
接下来m行，每行两个整数li,ri(1<=li,ri<=n)。（若li=ri，则不需要耗费任何时间）Output一个数表示答案。Sample Input
5 2
1 3
2 4
Sample Output
1 题解：
这个题目是不是和noip2015day2T3很像，于是我就打了一个差分＋二分，ｗａ了，怎么回事呢？因为他们不一定是区间的交，还有可能隧道不在区间的交中。
所以这个题目就特别难想了，当然如果我们还是二分一个答案ｍｉｄ很轻易的就可以列出不等式abs(stari-x)+abs(endi-y)<=mid，stari为ｉ号点的起点，endi为终点，ｘ为隧道起点，ｙ为隧道终点，那么显然对于满足所以１～ｉ合法的（ｘ，ｙ）整数点对的坐标就是这个题目的答案。
当然我们不需要用计算几何的知识，我们只需要讲这个不等式拆开，判短不等式是否成立就可以了。
这个题目还是比较神的，可以多思考一下，不要先看题解。 代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define MAXN 500100
#define inf 1<<30
using namespace std;
int n,m;
int l[MAXN],r[MAXN]; bool check(int mid){
int d1=-inf,d2=<<,c1=-inf,c2=<<;
for(int i=;i<=n;i++){
if(r[i]-l[i]<=mid) continue;
d1=max(d1,l[i]+r[i]-mid);
d2=min(d2,l[i]+r[i]+mid);
c1=max(l[i]-r[i]-mid,c1);
c2=min(l[i]-r[i]+mid,c2);
if(d1>d2) return ;
if(c1>c2) return ;
}
return ;
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++) scanf("%d%d",&l[i],&r[i]);
for(int i=;i<=m;i++){
if(l[i]>r[i]) swap(l[i],r[i]);
}
int l=,r=n,mid,ans=-;
while(l<=r){
mid=(l+r)/;
if(check(mid)) ans=mid,r=mid-;
else l=mid+;
}
printf("%d\n",ans);
return ;
}