You can intuitively understand the problem by plotting the data on a two-dimensional plane.

The following is a visualization of Sample Input/Output 1.

For cards \(x\) and \(y\), we have \(A_x > A_y\) and \(C_x < C_y\) if and only if the point corresponding to card \(x\) is in the lower-right region of that for card \(y\). In Sample Input/Output 1, card \(3\) is in the lower-right region of card \(1\).

Consider the condition of a card that is never discarded. By the discussion above, a card is never removed if there is no point on the lower-right region of the point for itself. Otherwise, the card is always removed.

The set of cards that has no point on its lower-right region can be found as follows. Scan the cards in ascending order of their costs, i.e. from lower points to higher, and include those that updates the maximum strength so far (the rightmost one) to the answer. (Not being able to update the maximum strength means there is a card with smaller cost and larger strength, i.e. there is a card on its lower-right region.)

• Sort cards in ascending order of \(C_i\). First, let \(v = 0\), and let \(S\) be an empty set.
• For \(i = 1, 2, \cdots ,N\) in order, if \(A_i > v\), then insert the \(i\)-th card, and set \(v\) to \(A_i\).
• The resulting \(S\) is the answer.

For sample code 1, it runs as follows.

• The cards are sorted by \(C_i\) as cards \(2, 3, 1\).
  • \(A_2 (= 1) > v (= 0)\), so insert card \(2\) to \(S\), and let \(v = 1\).
  • \(A_3 (= 3) > v (= 1)\), so insert card \(3\) to \(S\), and let \(v = 3\).
  • \(A_1 (= 2) < v (= 3)\), so card \(1\) is not inserted to \(S\).
• Finally, \(S = \{ 2, 3 \}\).

For example, it can be implemented in C++ as follows. The complexity is \(O(N \log N)\), where sorting is the bottleneck.

#include <bits/stdc++.h>

using namespace std;

struct Card {
    int a;
    int c;
    int index;
};

int main() {
    // Input
    int n;
    cin >> n;
    vector<Card> cards(n);
    for (int i = 0; i < n; ++i) {
        int a, c;
        cin >> a >> c;
        cards[i] = {a, c, i};
    }
    
    // Sort in ascending order of C[i]
    sort(cards.begin(), cards.end(), [&](const auto &l, const auto &r) {
        return l.c < r.c;
    });
    
    // Compute the answer
    vector<int> ans;
    int v = 0;
    for (int i = 0; i < n; ++i) {
        if (cards[i].a > v) {
            v = cards[i].a;
            ans.push_back(cards[i].index);
        }
    }
    sort(ans.begin(), ans.end());
    
    // Print
    const int m = (int)ans.size();
    cout << m << endl;
    for (int i = 0; i < m; ++i) {
        cout << ans[i] + 1;
        if (i == m - 1) {
            cout << endl;
        } else {
            cout << ' ';
        }
    }
}