记录编号	578298	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]问题A	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.179 s
提交时间	2023-03-02 16:43:15	内存使用	8.09 MiB

// Problem: P2519 [HAOI2011]problem a
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2519
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

const int maxn = 1e5 + 5;
int n,f[maxn];
std::map<int,int> seg[maxn];

int main() {
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	scanf("%d",&n);
	for(int i = 1;i <= n;++ i) {
		int x,y;
		scanf("%d %d",&x,&y);
		x = x + 1;
		y = n - y;
		if(x > y)
			continue ;
		++ seg[y][x];
	}
	for(int i = 1;i <= n;++ i) {
		f[i] = f[i - 1];
		for(auto& [x , v] : seg[i])
			f[i] = std::max(f[i] , f[x - 1] + std::min(v , i - x + 1));
	}
	printf("%d\n",n - f[n]);
	return 0;
}