#include #include #include #include using namespace std; struct Doll { int r, R; }; // Comparator to sort dolls by outer diameter bool compareDolls(const Doll& a, const Doll& b) { return a.R < b.R; } int minScalingOperations(vector& dolls) { int n = dolls.size(); // Sort dolls based on their outer diameters sort(dolls.begin(), dolls.end(), compareDolls); vector dp(n, INT_MAX); dp[0] = 0; // No scaling needed for the first doll for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { if (dolls[j].R <= dolls[i].r) { dp[i] = min(dp[i], dp[j]); } } // Consider scaling operation if no valid nesting found if (dp[i] == INT_MAX) { dp[i] = dp[i-1] + 1; } } return dp[n-1]; } int main() { int N; cin >> N; vector dolls(N); for (int i = 0; i < N; ++i) { cin >> dolls[i].r >> dolls[i].R; } int result = minScalingOperations(dolls); cout << result << endl; return 0; }