#include using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); return 0; } using ll = long long; using ull = unsigned long long; using ld = long double; using vi = std::vector; using vvi = std::vector; using vl = std::vector; using vii = std::vector >; using vvl = std::vector; using vll = std::vector >; using vd = std::vector; using vvd = std::vector; using vs = std::vector; using vvs = std::vector; using vb = std::vector; using vvb = std::vector; using vc = std::vector; using vvc = std::vector; using pii = std::pair; using pll = std::pair; using piil = std::pair, ll>; using mii = std::map; using mll = std::map; using pql = std::priority_queue; using pqi = std::priority_queue; using pqiil = std::priority_queue, ll> >; using pqii = std::priority_queue >; #define pb push_back #define ps push #define eb emplace_back #define is insert #define er erase #define f first #define s second #define lb lower_bound #define ub upper_bound #define sf(i) sizeof(i) #define endl "\n" #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() #define rep(i, L, R) for(ll i = L;i<=R;i++) #define pcis precision template struct infinity { static constexpr T max=std::numeric_limits::max(); static constexpr T min=std::numeric_limits::min(); static constexpr T value=std::numeric_limits::max()/2; static constexpr T mvalue=std::numeric_limits::min()/2; }; templateconstexpr T INF=infinity::value; constexpr ll lINF=INF; constexpr int iINF = INF; constexpr ld PI = 3.1415926535897932384626; void _main() { ll N; cin >> N; pll A[N+1]; for (ll i = 1; i<=N; i++)cin>>A[i].f>>A[i].s; // 일단 내경 순서대로 정리? // 제일 작은거는? sort(A+1,A+N+1); // B는 사실상 없애는거임 // 내경 작은 순 (? // 외경 작은 순이 나은가? // 스위핑 느낌으로 하면 될듯 // 내경이 같다면 // 겹치지 않고 놓을 수 있는 최대 막대 개수를 구하면 됨 // 짧은걸로 두는게 이득 stack stk; // 없애는거끼리 또 붙일 수 있음! // 그 어떤 거에도 못붙이는 애를 찾아야하나? 아닌데 // 붙일 수 있는애가 있으면 붙임 => 아니면 안붙임? // R좌표순 정렬? // 간선을 미리 이어둘 수 있나 multiset se;// 끝점들만 모아둠 for (ll i = 1; i<=N; i++) { auto [a,b] = A[i]; // r 제일 작은거보다 작으면 => 못붙임 // 아니면? 걔에다 붙임? if (se.empty()) { se.is(b); } else { // 끝점이 a 이하여야 함 multiset::iterator iter = se.lb(a); if (iter == se.begin()) { if ((*iter) == a) { // 삭제해도 됨 se.erase(iter); } } else { if (iter == se.end() || (*iter) != a) { // 전으로 감 iter = prev(iter); se.erase(iter);// 그거 지움 } else { // 그대로 있는게 이득 se.erase(iter);// 그거 지움 } } se.is(b); } } cout << se.size()-1 << endl; }