我们为每个考生设置一个可能的区间。这个区间的左端点是l=a+1，右端点是r=n-b。
仔细观察，会发现，这个可能的区间，就是和这个考生同分（包括这个考生）的考生的数量。
那么显然，如果这个可能的区间不存在，那么这个考生在撒谎；如果在同一个区间里面有超过区间长度的考生数，那么也是不合法的。
我们仔细想想，还有什么情况是冲突的。我们发现，说真话的考生所在的区间是不能重合的。
于是问题就转化为一个类似于背包的问题。我们可以将这些区间排序，那么不妨设f[i]表示第i个区间为真的情况下的最大数量。
首先，如果右端点递减，我们可以考虑用一个单调队列来维护这个东西。
在这种情况下，可以维护一个r值递增，f值递增的单调队列。
每一次把新的右端点插入到单调队列的右端，然后如果右端的f值比当前的f值小，那么就把右端的f值给干掉。
然而，实际上，右端点是无单调性的，所以可能存在这样一种情况：新插入的点的r值更小，而f值也更小。这时候就没有办法判断是否要删掉单调队列末端的点了。
想象一下在这种情况下要怎么做。在这种情况下，我们可以将新插入的点插到r值刚好比它小的那个点前面，然后把所有r值比它大而f值比它小的点都删掉。
要如何维护呢？直观地想是使用平衡树，但是我们可以使用map来完成这个操作。
然而，这样涉及到复杂的iterator操作。我并不是很会。
我们考虑另外一种想法。我们令f[i]表示以i为当前访问过的最右端点的情况下的最优值。
那么，我们可以记录每一个右端点的所有左端点，然后枚举这些左端点并转移，就可以得出答案。
注意：一个区间的权值要与它的长度取min！
注意：这样求出来的答案是真的数量，要用n减去它！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;
inline int Max(int A,int B){
return A>B?A:B;
}
inline int Min(int A,int B){
return A<B?A:B;
}
typedef pair<int,int> pii;
const int N=100005;
int n;
int f[N];
vector<int> lst[N];
map<pii,int> mp;
void init(){
scanf("%d",&n);
int x,y,l,r;
for(int i=1;i<=n;++i){
scanf("%d%d",&x,&y);
l=x+1,r=n-y;
if(l>r){
continue;
}
if(++mp[(pii){l,r}]==1){
lst[r].push_back(l);
}
}
for(int i=1;i<=n;++i){
f[i]=f[i-1];
for(int j=0;j<lst[i].size();++j){
f[i]=Max(f[i],f[lst[i][j]-1]+Min(i-lst[i][j]+1,mp[(pii){lst[i][j],i}]));
}
}
printf("%d\n",n-f[n]);
}
int main(){
init();
return 0;
}