#pragma region template #ifdef USE_PRECOMPILE #include "pch.h" #else #pragma GCC optimize("Ofast") #include using namespace std; using ll = long long; using ld = long double; using vi = std::vector; using vll = std::vector; template using PA = std::pair; using pi = PA; using pll = PA; #define overload2(a, b, c, ...) c #define overload3(a, b, c, d, ...) d #define overload4(a, b, c, d, e, ...) e #define overload5(a, b, c, d, e, f, ...) f #define TYPE1(T) template #define TYPE2(T, U) template #define TYPE(...) overload2(__VA_ARGS__, TYPE2, TYPE1)(__VA_ARGS__) #define TYPES1(T) template #define TYPES2(H, T) template #define TYPES(...) overload2(__VA_ARGS__, TYPES2, TYPES1)(__VA_ARGS__) #define REP4(i, s, n, d) for (int i = (s); i < (n); i += (d)) #define REP3(i, s, n) REP4(i, s, n, 1) #define REP2(i, n) REP3(i, 0, n) #define REP1(n) REP2(tomato, n) #define REP(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__) #define RREP4(i, n, s, d) for (int i = (n) - 1; i >= (s); i -= (d)) #define RREP3(i, n, s) RREP4(i, n, s, 1) #define RREP2(i, n) RREP3(i, n, 0) #define RREP1(n) RREP2(tomato, n) #define RREP(...) \ overload4(__VA_ARGS__, RREP4, RREP3, RREP2, RREP1)(__VA_ARGS__) #define FOR4(a, b, c, d, v) for (auto [a, b, c, d] : v) #define FOR3(a, b, c, v) for (auto [a, b, c] : v) #define FOR2(a, b, v) for (auto [a, b] : v) #define FOR1(a, v) for (auto a : v) #define FOR(...) overload5(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__) #define AFOR4(a, b, c, d, v) for (auto &[a, b, c, d] : v) #define AFOR3(a, b, c, v) for (auto &[a, b, c] : v) #define AFOR2(a, b, v) for (auto &[a, b] : v) #define AFOR1(a, v) for (auto &a : v) #define AFOR(...) \ overload5(__VA_ARGS__, AFOR4, AFOR3, AFOR2, AFOR1)(__VA_ARGS__) #define CFOR4(a, b, c, d, v) for (const auto &[a, b, c, d] : v) #define CFOR3(a, b, c, v) for (const auto &[a, b, c] : v) #define CFOR2(a, b, v) for (const auto &[a, b] : v) #define CFOR1(a, v) for (const auto &a : v) #define CFOR(...) \ overload5(__VA_ARGS__, CFOR4, CFOR3, CFOR2, CFOR1)(__VA_ARGS__) #define RFOR4(a, b, c, d, v) for (auto [a, b, c, d] : v | std::views::reverse) #define RFOR3(a, b, c, v) for (auto [a, b, c] : v | std::views::reverse) #define RFOR2(a, b, v) for (auto [a, b] : v | std::views::reverse) #define RFOR1(a, v) for (auto a : v | std::views::reverse) #define RFOR(...) \ overload5(__VA_ARGS__, RFOR4, RFOR3, RFOR2, RFOR1)(__VA_ARGS__) #define RAFOR4(a, b, c, d, v) for (auto &[a, b, c, d] : v | std::views::reverse) #define RAFOR3(a, b, c, v) for (auto &[a, b, c] : v | std::views::reverse) #define RAFOR2(a, b, v) for (auto &[a, b] : v | std::views::reverse) #define RAFOR1(a, v) for (auto &a : v | std::views::reverse) #define RAFOR(...) \ overload5(__VA_ARGS__, RAFOR4, RAFOR3, RAFOR2, RAFOR1)(__VA_ARGS__) #define RCFOR4(a, b, c, d, v) \ for (const auto &[a, b, c, d] : v | std::views::reverse) #define RCFOR3(a, b, c, v) for (const auto &[a, b, c] : v | std::views::reverse) #define RCFOR2(a, b, v) for (const auto &[a, b] : v | std::views::reverse) #define RCFOR1(a, v) for (const auto &a : v | std::views::reverse) #define RCFOR(...) \ overload5(__VA_ARGS__, RCFOR4, RCFOR3, RCFOR2, RCFOR1)(__VA_ARGS__) #define ALL(v) v.begin(), v.end() #define RALL(v) v.rbegin(), v.rend() #define SORT(v) std::ranges::sort(v) #define RSORT(v) sort(RALL(v)) #define REVERSE(v) std::ranges::reverse(v) #define UNIQUE(v) SORT(v), v.erase(unique(ALL(v)), v.end()) #define SZ(v) int(v.size()) #define MAX(v) std::ranges::max(v) #define MIN(v) std::ranges::min(v) template std::conditional_t, ll, T> SUM(const std::vector &v) { return std::accumulate( ALL(v), std::conditional_t, ll, T>(0)); } TYPES(T) void input(T &...a) { (std::cin >> ... >> a); } #define DECLARE(T, ...) \ T __VA_ARGS__; \ input(__VA_ARGS__); #define INT(...) DECLARE(int, __VA_ARGS__) #define STR(...) DECLARE(std::string, __VA_ARGS__) #define LL(...) DECLARE(long long, __VA_ARGS__) #define CHR(...) DECLARE(char, __VA_ARGS__) #define DBL(...) DECLARE(double, __VA_ARGS__) #define VI(n, v) \ vi v(n); \ std::cin >> v; #define VLL(n, v) \ vll v(n); \ std::cin >> v; #define VS(n, s) \ std::vector s(n); \ std::cin >> s; TYPE(T, S) std::istream &operator>>(std::istream &is, std::pair &p) { is >> p.first >> p.second; return is; } TYPE(T, S) std::ostream &operator<<(std::ostream &os, const std::pair &p) { os << p.first << " " << p.second; return os; } TYPE(T) istream &operator>>(std::istream &is, std::vector &v) { for (auto &a : v) std::cin >> a; return is; } TYPE(T) std::ostream &operator<<(std::ostream &os, const std::vector &v) { if (&os == &std::cerr) os << "["; REP (i, v.size()) { os << v[i]; if (i + 1 < v.size()) os << (&os == &std::cerr ? "," : " "); } if (&os == &std::cerr) os << "]"; return os; } #ifdef __DEBUG #include #else #define debug(...) void(0) #endif void print() { cout << '\n'; } TYPES(T, Ts) void print(const T &a, const Ts &...b) { std::cout << a; (std::cout << ... << (std::cout << ' ', b)); std::cout << '\n'; } TYPE(T) using pq = std::priority_queue; TYPE(T) using pqg = std::priority_queue, std::greater>; TYPE(T) T pick(std::queue &que) { assert(que.size()); T a = que.front(); que.pop(); return a; } TYPE(T) T pick(pq &que) { assert(que.size()); T a = que.top(); que.pop(); return a; } TYPE(T) T pick(pqg &que) { assert(que.size()); T a = que.top(); que.pop(); return a; } TYPE(T) T pick(std::stack &sta) { assert(sta.size()); T a = sta.top(); sta.pop(); return a; } TYPE(T) void clear(T &v) { v = decltype(v)(); } std::string YES(bool f = true) { return (f ? "YES" : "NO"); } std::string Yes(bool f = true) { return (f ? "Yes" : "No"); } std::string yes(bool f = true) { return (f ? "yes" : "no"); } constexpr int INF = 1e9 + 7; constexpr ll LINF = ll(1e18) + 7; constexpr ld EPS = 1e-10; vi iota(int n) { vi a(n); std::iota(ALL(a), 0); return a; } TYPE(T) void add(std::vector &v, T a = 1) { AFOR (p, v) p += a; } TYPE(T) T rev(T a) { REVERSE(a); return a; } TYPE(T) void fin(T a) { std::cout << a << '\n'; exit(0); } TYPE(T) bool chmax(T &a, T b) { return (a < b && (a = b, true)); } TYPE(T) bool chmin(T &a, T b) { return (a > b && (a = b, true)); } TYPES(T, Ns) auto make_vector(T x, int n, Ns... ns) { if constexpr (sizeof...(ns) == 0) return std::vector(n, x); else return std::vector(n, make_vector(x, ns...)); } bool in(const ll S, const int a) { return (S >> a) & 1; } int digit(char c) { return (c >= '0' and c <= '9' ? c - '0' : -1); } void signal_hander(int signal) { std::exit(EXIT_FAILURE); } #endif #pragma endregion template int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::signal(SIGABRT, signal_hander); std::map> mp; int n; std::cin >> n; REP (n) { INT(r, R); mp[r].push(R); } int ans = 0; while (mp.size()) { ans++; auto it = mp.begin(); int r = it->first; int R = pick(it->second); if (!(it->second.size())) mp.erase(r); while (true) { auto it = mp.lower_bound(R); if (it == mp.end()) break; R = pick(it->second); if (!(it->second.size())) mp.erase(it); } } std::cout << ans - 1 << '\n'; }