You are given $n$ pairs of integers $(a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n)$. All of the integers in the pairs are distinct and are in the range from $1$ to $2 \cdot n$ inclusive.
Let’s call a sequence of integers $x_1, x_2, \ldots, x_{2k}$ good if either
- $x_1 < x_2 > x_3 < \ldots < x_{2k-2} > x_{2k-1} < x_{2k}$, or
- $x_1 > x_2 < x_3 > \ldots > x_{2k-2} < x_{2k-1} > x_{2k}$.
You need to choose a subset of distinct indices $i_1, i_2, \ldots, i_t$ and their order in a way that if you write down all numbers from the pairs in a single sequence (the sequence would be $a_{i_1}, b_{i_1}, a_{i_2}, b_{i_2}, \ldots, a_{i_t}, b_{i_t}$), this sequence is good.
What is the largest subset of indices you can choose? You also need to construct the corresponding index sequence $i_1, i_2, \ldots, i_t$.
Input
The first line contains single integer $n$ ($2 \leq n \leq 3 \cdot 10^5$) — the number of pairs.
Each of the next $n$ lines contain two numbers — $a_i$ and $b_i$ ($1 \le a_i, b_i \le 2 \cdot n$) — the elements of the pairs.
It is guaranteed that all integers in the pairs are distinct, that is, every integer from $1$ to $2 \cdot n$ is mentioned exactly once.
Output
In the first line print a single integer $t$ — the number of pairs in the answer.
Then print $t$ distinct integers $i_1, i_2, \ldots, i_t$ — the indexes of pairs in the corresponding order.
Examples
input
5 1 7 6 4 2 10 9 8 3 5
output
3 1 5 3
input
3 5 4 3 2 6 1
output
3 3 2 1
Note
The final sequence in the first example is $1 < 7 > 3 < 5 > 2 < 10$.
The final sequence in the second example is $6 > 1 < 3 > 2 < 5 > 4$.
Solution:
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n); vector<int> b(n); vector<int> lt; vector<int> gt; for (int i = 0; i < n; i++) { cin >> a[i] >> b[i]; if (a[i] < b[i]) { lt.push_back(i); } else { gt.push_back(i); } } vector<int> ans; if (lt.size() > gt.size()) { sort(lt.begin(), lt.end(), [&](int i, int j) { return b[i] > b[j]; }); ans = lt; } else { sort(gt.begin(), gt.end(), [&](int i, int j) { return a[i] < a[j]; }); ans = gt; } cout << ans.size() << '\n'; for (int i = 0; i < (int) ans.size(); i++) { if (i > 0) { cout << " "; } cout << ans[i] + 1; } cout << '\n'; return 0; }