### 题目描述

$1≤n≤100000$,
$10^{-9}≤l_i≤r_i≤10{9}$

#### 输入样例

5
1 2
2 4
5 6
7 8
7 9


#### 输出样例

3


### 算法

#### C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
#define l first
#define r second
using namespace std;
typedef pair<int, int> pii;
int n, x, y, res = 0, k = 0;
vector<pii> vec;

int main() {
scanf("%d", &n);
if(n == 1) {
printf("0\n");
return 0;
}
for (int i = 0; i < n; i ++) {
scanf("%d%d", &x, &y);
vec.push_back({x, y});
}
sort(vec.begin(), vec.end());
int maxr = vec[0].l;
for(int i = 1; i < n; i ++) {
pii cur = vec[i], last = vec[i-1];
maxr = max(maxr, last.r);
if(cur.l <= maxr) k ++;
else    k = 1;
if(k == 1) {
maxr = cur.l;
res ++;
}
}
printf("%d\n", res);
return 0;
}


#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#define l first
#define r second
using namespace std;
typedef pair<int, int> pii;
int n, x, y, res = 0, k = 0;
vector<pii> vec;

int main() {
scanf("%d", &n);
if(n == 1) {
printf("0\n");
return 0;
}
for (int i = 0; i < n; i ++) {
scanf("%d%d", &x, &y);
vec.push_back({x, y});
}
sort(vec.begin(), vec.end());
int maxr = vec[0].l;
for(int i = 1; i < n; i ++) {
pii cur = vec[i], last = vec[i-1];
maxr = max(maxr, last.r);
if(cur.l <= maxr) k ++;
else    k = 1;
if(k == 1) {
maxr = cur.l;
res ++;
}
//cout << "第" << i << "组测试：" << cur.l << ' ' << cur.r << " 结果" << res << endl;
}
printf("%d\n", res);
return 0;
}


#include <iostream>
#include <algorithm>
#include <vector>
#define key first
#define val second
using namespace std;
typedef pair<int, int> PII;
const int N = 3e5+10;
int n, m;
vector<int> alls;       // 离散化前的所有数
int a[N], s[N];

int find(int k) {
int l = 0, r = alls.size() - 1;
while(l < r) {
int mid = l+r >> 1;
if(alls[mid] >= k) r = mid;
else    l = mid + 1;
}
return r + 1;
}

int main() {
int x, c, l, r, len;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++) {
scanf("%d%d", &x, &c);
ass.push_back({x,c});
alls.push_back(x);
}
for (int i = 0; i < m; i ++) {
scanf("%d%d", &l, &r);
alls.push_back(l);
alls.push_back(r);
}
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
len = alls.size();
for (auto item : ass) {
a[find(item.key)] += item.val;
}
for (int i = 1; i <= len; i ++) {
s[i] = s[i-1] + a[i];
}
for (auto item : ask) {
l = find(item.key), r = find(item.val);
printf("%d\n", s[r] - s[l-1]);
}

return 0;
}


#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+5;
int a[N], b[N];
int n, m, x;

int main() {
scanf("%d%d%d", &n, &m, &x);
for (int i = 0; i < n; i ++)
scanf("%d", &a[i]);
for (int i = 0; i < m; i ++)
scanf("%d", &b[i]);
for(int i = 0, j = m - 1; i < n; i ++) {
while(j >= 0 && a[i] + b[j] > x)   j --;
if(a[i] + b[j] == x) {
printf("%d %d\n", i, j);
return 0;
}
}
return 0;
}


#include <iostream>
using namespace std;

int lowbit(int n) {
return n & -n;
}

int main() {
int n, k;
scanf("%d", &n);
while(n --) {
scanf("%d", &k);
int cnt = 0;
while(k != 0) {
k -= lowbit(k);
cnt ++;
}
printf("%d ", cnt);
}
return 0;
}


#include <iostream>
using namespace std;
const int N = 1e5+5;
int a[N], s[N];
int n, res = 0;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i ++)
scanf("%d", &a[i]);
for (int i = 0, j = 0; i < n; i ++) {
s[a[i]] ++;
while(s[a[i]] > 1) {
s[a[j]] --;
j ++;
}
res = max(res, i - j + 1);
}
printf("%d\n", res);
return 0;
}


#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c) {
b[x1][y1] += c;
b[x2+1][y1] -= c;
b[x1][y2+1] -= c;
b[x2+1][y2+1] += c;
}
int main() {
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++) {
scanf("%d", &a[i][j]);
insert(i, j, i, j, a[i][j]);
}
while(q --) {
int x1, y1, x2, y2, c;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
insert(x1, y1, x2, y2, c);
}
for(int i = 1; i<= n; i ++)
for(int j = 1; j <= m; j ++)
b[i][j] =  b[i][j-1] + b[i-1][j] - b[i-1][j-1] + b[i][j];
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++)
printf("%d ", b[i][j]);
puts("");
}
return 0;
}



#include <iostream>
using namespace std;
const int N = 1e5+10;
int a[N], b[N];
void insert(int l, int r, int c) {
b[l] += c;
b[r+1] -= c;
}

int main() {
int n, m, l, r, c;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
insert(i, i, a[i]);
}
while(m--) {
scanf("%d%d%d", &l, &r, &c);
insert(l, r, c);
}
for(int i = 1; i <= n; i ++)
b[i] += b[i-1];
for(int i = 1; i <= n; i ++)
printf("%d ", b[i]);
return 0;
}


#include <iostream>
using namespace std;
const int N = 1e3+5;
int a[N][N], s[N][N];
int n, m, q;
int main() {
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
scanf("%d", &a[i][j]);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
s[i][j] = s[i][j-1] + s[i-1][j] -s[i-1][j-1] + a[i][j];
while(q --) {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]);
}
return 0;
}


#include <iostream>
using namespace std;
const int N = 1e5+5;
int a[N], s[N];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++)
scanf("%d", &a[i]);
for(int i = 1; i <= n; i ++)
s[i] = s[i-1] + a[i];
while(m --) {
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", s[r] - s[l-1]);
}
return 0;
}