<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

99. Beautiful People
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



The most prestigious sports club in one city has exactly N members. Each of its members is strong and beautiful. More precisely, i-th member of this club (members being numbered by the time they entered the club) has strength Si and beauty Bi . Since this is a very prestigious club, its members are very rich and therefore extraordinary people, so they often extremely hate each other. Strictly speaking, i-th member of the club Mr X hates j-th member of the club Mr Y if Si ≤ Sj and Bi ≥ Bj or if Si ≥ Sj and Bi ≤ Bj (if both properties of Mr X are greater then corresponding properties of Mr Y, he doesn't even notice him, on the other hand, if both of his properties are less, he respects Mr Y very much).

To celebrate a new 2003 year, the administration of the club is planning to organize a party. However they are afraid that if two people who hate each other would simultaneouly attend the party, after a drink or two they would start a fight. So no two people who hate each other should be invited. On the other hand, to keep the club presti≥ at the apropriate level, administration wants to invite as many people as possible.

Being the only one among administration who is not afraid of touching a computer, you are to write a program which would find out whom to invite to the party.

Input

The first line of the input file contains integer N — the number of members of the club. ( 2 ≤ N ≤ 100,000 ). Next N lines contain two numbers each — Si and Bi respectively ( 1 ≤ Si, Bi ≤ 109 ).

Output

On the first line of the output file print the maximum number of the people that can be invited to the party. On the second line output N integers — numbers of members to be invited in arbitrary order. If several solutions exist, output any one.

Sample test(s)

Input

4
1 1
1 2
2 1
2 2

Output

2
1 4
Author:	Andrew Stankevich
Resource:	Petrozavodsk Winter Trainings 2003
Date:	2003-02-06

<|response|>
1. Abridged Problem Statement
You have N club members, each described by strength Si and beauty Bi. Two members hate each other if one is at least as strong but not more beautiful, or at least as beautiful but not more strong. You must select the largest possible subset with no hateful pair. Output its size and any valid set of original indices.

2. Key Observations
- A hateful pair corresponds to a non-strict ordering conflict in the two attributes: one member does not strictly dominate the other in both.
- To avoid any hate, within the invited subset both strength and beauty must strictly increase from one member to the next.
- Finding the largest such subset is exactly finding a maximum-length chain in the partial order (Si < Sj and Bi < Bj).
- By sorting members by strength ascending (and for equal strength by beauty descending), the problem reduces to finding a Longest Increasing Subsequence (LIS) on the beauty values.

3. Full Solution Approach
a. Read N and the list of triples (Si, Bi, originalIndex).
b. Sort the list by
   - primary key: strength ascending
   - secondary key: beauty descending
  This ensures that for members with equal strength you cannot take more than one (because beauties go down).
c. Extract the beauty array in sorted order.
d. Compute the LIS on this beauty array in O(N log N) using the “patience sorting” method with a tail array and binary search:
   - Maintain an array tail[], where tail[len] is the minimum possible ending beauty of an increasing subsequence of length len+1.
   - For each beauty b at index i, find the insertion position pos = lower_bound(tail, b).
   - Record pos as the chain length (minus one) achieved by element i.
   - If pos equals the current LIS length, append b to tail; otherwise overwrite tail[pos] = b.
e. After processing all members, the length of tail[] is the maximum invite count.
f. Reconstruct one LIS by scanning the (sorted) array from the back: keep a target length equal to the current LIS length, and whenever an element’s recorded pos equals target−1, take it and decrement target. Reverse the collected original indices.
g. Print the LIS length and the list of original indices.

4. C++ Implementation
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<array<int, 3>> a;

void read() {
    cin >> n;
    a.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1];
        a[i][2] = i + 1;
    }
}

void solve() {
    // - We want the largest subset that can be totally ordered with both
    //   strength and beauty strictly increasing (any two members where one
    //   dominates strictly in both coexist; ties in either coordinate make them
    //   hate each other). This is a longest strictly-increasing chain in 2D.
    //
    // - Sort by strength ascending, breaking ties by beauty descending so that
    //   equal-strength members can never be picked together in a strictly
    //   increasing beauty run. Then a standard O(n log n) longest strictly
    //   increasing subsequence on the beauty values gives the answer length,
    //   with pos[i] recording the chain length ending at element i.
    //
    // - Reconstruct by scanning from the back, peeling off elements whose pos
    //   matches the current target length, then reversing to restore order and
    //   printing their original indices.

    sort(a.begin(), a.end(), [&](auto x, auto y) {
        if(x[0] != y[0]) {
            return x[0] < y[0];
        }
        return x[1] > y[1];
    });

    vector<int> lis;
    vector<int> pos(n, -1);
    for(int i = 0; i < n; i++) {
        auto it = lower_bound(lis.begin(), lis.end(), a[i][1]);
        pos[i] = it - lis.begin();
        if(it == lis.end()) {
            lis.push_back(a[i][1]);
        } else {
            *it = a[i][1];
        }
    }

    int len = lis.size();
    vector<int> ans;
    for(int i = n - 1; i >= 0; i--) {
        if(pos[i] == len - 1) {
            ans.push_back(a[i][2]);
            len--;
        }
    }

    reverse(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments
```python
import sys
import bisect

def main():
    input = sys.stdin.readline
    N = int(input())

    # Read members as (strength, beauty, original_index)
    members = []
    for i in range(N):
        s, b = map(int, input().split())
        members.append((s, b, i + 1))

    # Sort by strength ascending, beauty descending on ties
    members.sort(key=lambda x: (x[0], -x[1]))

    # tailBeauty will store the tail values of increasing subsequences
    tailBeauty = []
    # tailIndex[len] = index in members where an LIS of length len+1 ends
    tailIndex = []
    # prevIdx[i] = predecessor index in members for reconstructing the LIS ending at i
    prevIdx = [-1] * N

    for i, (s, b, orig) in enumerate(members):
        # Find insertion point for b
        pos = bisect.bisect_left(tailBeauty, b)
        if pos == len(tailBeauty):
            # extend tailBeauty and record this end-index
            tailBeauty.append(b)
            tailIndex.append(i)
        else:
            # replace to keep the smallest possible tail
            tailBeauty[pos] = b
            tailIndex[pos] = i

        # link to the previous element in the LIS of length pos
        if pos > 0:
            prevIdx[i] = tailIndex[pos - 1]

    lisLen = len(tailBeauty)
    result = []
    # start reconstruction from the last element of the LIS
    idx = tailIndex[lisLen - 1]
    while idx != -1:
        # collect original index
        result.append(members[idx][2])
        idx = prevIdx[idx]

    # reverse to get correct order
    result.reverse()

    # Output
    print(lisLen)
    print(*result)

if __name__ == "__main__":
    main()
```
