每天，农夫约翰的 NN 头奶牛都会穿过农场中间的马路。
考虑约翰的农场在二维平面的地图，马路沿水平方向延伸，马路的一侧由直线 y=0y=0 描述，另一侧由直线 y=1y=1 描述。
奶牛 ii 从马路一侧的位置 (ai,0)(ai,0) 沿直线过马路到达另一侧的位置 (bi,1)(bi,1)。
所有 aiai 互不相同，所有 bibi 互不相同。
尽管他的奶牛们行动敏捷，他还是担心行动路径交叉的两头奶牛在过马路时发生碰撞。
约翰认为，如果一头奶牛的行动路径没有跟其他任何奶牛的行动路径相交，则该奶牛是安全的。
请帮助约翰计算安全奶牛的数量。

输入格式

第一行包含整数 NN。
接下来 NN 行，每行包含两个整数 ai,biai,bi，用来描述一头牛的行动路径。

输出格式

输出安全奶牛的数量。

数据范围

1≤N≤1051≤N≤105,
−106≤ai,bi≤106−106≤ai,bi≤106

输入样例：

4 -3 4 7 8 10 16 3 9

输出样例：

2

样例解释

第一头牛和第三头牛的行动路线不与其他奶牛的路线相交。
第二头牛和第四头牛的行动路线相交。

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  5. #define x first
  6. #define y second
  8. using namespace std;
  10. typedef pair<int,int> PII;
  12. const int N = 100010, INF = 1e8;
  14. int n;
  15. PII q[N];
  16. int smax[N],smin[N];
  18. int main() {
  19.     cin >> n;
  20.     for (int i = 1; i <= n; ++i) cin >> q[i].x >> q[i].y;
  21.     //排序
  22.     sort(q+1,q+n+1);
  24.     smax[0] = -INF, smin[n+1] = INF;
  25.     //最大前缀值，最小前缀值
  26.     for (int i = 1; i <= n; ++i) smax[i] = max(smax[i-1],q[i].y);
  27.     for (int i = n; i > 0; --i) smin[i] = min(smin[i+1],q[i].y);
  29.     int res = 0;
  30.     for (int i = 1; i <= n; ++i) 
  31.         if (q[i].y > smax[i-1] && q[i].y < smin[i+1]) 
  32.             res++;
  33.     cout << res << endl;
  34.     return 0;
  35. }