Problem: You are given n pairs of integers (a_1, b_1), (a_2, b_2), …, (a_n, b_n). All of the integers in the pairs are distinct and are in the range from 1 to 2 ⋅ n inclusive.

Let's call a sequence of integers x_1, x_2, …, x_{2k} good if either 

  * x_1 < x_2 > x_3 < … < x_{2k-2} > x_{2k-1} < x_{2k}, or 
  * x_1 > x_2 < x_3 > … > x_{2k-2} < x_{2k-1} > x_{2k}. 



You need to choose a subset of distinct indices i_1, i_2, …, 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}, …, 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, …, i_t.

Input

The first line contains single integer n (2 ≤ n ≤ 3 ⋅ 10^5) — the number of pairs.

Each of the next n lines contain two numbers — a_i and b_i (1 ≤ a_i, b_i ≤ 2 ⋅ 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 ⋅ 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, …, 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 (in JAVA):

Solution:
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;

public class Codeforces {

    static double Phi = (1 + Math.sqrt(5)) / 2.0;
    static int MAX = -1 >>> 1;
    static long MODL = 1_000_000_007L;
    static int MOD = 1_000_000_007;
    static void no() throws IOException {println("NO");}
    static void yes() throws IOException {println("YES");}

    static boolean testCases = false;
    static boolean DEBUG = false;

    static class Item {
        int a;
        int b;
        int i;
        Item(int a, int b, int i) {
            this.a = a;
            this.b = b;
            this.i = i;
        }
    }
    static void main() throws Exception {
        int n = ni();
        Item[] arr = new Item[n];
        List<Item> left = new ArrayList<>();
        List<Item> right = new ArrayList<>();

        for (int i = 0; i < n; ++i) {
            arr[i] = new Item(ni(), ni(), i);
            if(arr[i].a < arr[i].b) {
                left.add(arr[i]);
            } else {
                right.add(arr[i]);
            }
        }
        List<Item> ans;
        if(left.size() > right.size()) {
            Collections.sort(left, (o1, o2) -> {
                return -Integer.compare(o1.b, o2.b);
            });
            ans = left;
        } else {
            Collections.sort(right, (o1, o2) -> {
                return Integer.compare(o1.a, o2.a);
            });
            ans = right;
        }
        println(ans.size());
        for(Item i : ans) {
            print(i.i + 1 + " ");
        }
    }

    public static void main(String[] args) throws Exception {
        long startPointTime = System.currentTimeMillis();
        scannerIn = System.in;
        printerBW = new BufferedWriter(new OutputStreamWriter(System.out));
        if (DEBUG && System.getenv("HABLA") != null) {
            HABLA = true;
            debug("Automatic debugging " + System.getenv("HABLA"));
        }

        int t = testCases ? ni() : 1;
        int to = t;
        while (t-- > 0) {
            debug("Case #" + (to - t) + " ---------------- ");
            main();
        }
        long endTime = System.currentTimeMillis();
        float totalProgramTime = endTime - startPointTime;
        if (args.length > 0 && args[0].equalsIgnoreCase("time") || args.length > 1 && args[1].equalsIgnoreCase("time"))
            print("Execution time is " + totalProgramTime + " (" + (totalProgramTime / 1000) + "s)");
        close();
    }
//            /$$
//           | $$
//   /$$$$$$$| $$  /$$$$$$   /$$$$$$$ /$$$$$$$  /$$$$$$   /$$$$$$$
//  /$$_____/| $$ |____  $$ /$$_____//$$_____/ /$$__  $$ /$$_____/
// | $$      | $$  /$$$$$$$|  $$$$$$|  $$$$$$ | $$$$$$$$|  $$$$$$
// | $$      | $$ /$$__  $$ \____  $$\____  $$| $$_____/ \____  $$
// |  $$$$$$$| $$|  $$$$$$$ /$$$$$$$//$$$$$$$/|  $$$$$$$ /$$$$$$$/
//  \_______/|__/ \_______/|_______/|_______/  \_______/|_______/


    static class Pair {
        int a;
        int b;
        Pair(Pair x) {
            this.a = x.a;
            this.b = x.b;
        }
        Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
        public String toString() {
            return a + "(" + b + ")";
        }
    }
    static class DisjointSet {
        int[] arr;
        int[] size;
        boolean enableSize = true;

        DisjointSet(int n) {
            arr = new int[n + 1];
            this.enableSize = enableSize;
            if (this.enableSize) size = new int[n + 1];
            makeSet();
        }

        void makeSet() {
            for (int i = 1; i < arr.length; i++) {
                arr[i] = i;
                if (enableSize) size[i] = 1;
            }
        }

        void union(int i, int j) {
            i = find(i);
            j = find(j);

            if (i == j)
                return;
            arr[j] = arr[i];
            if (enableSize) {
                size[i] += size[j];
                size[j] = size[i];
            }
        }

        int find(int i) {
            if (i == arr[i]) return i;
            return arr[i] = find(arr[i]);
        }

        int getSize(int i) {
            if (enableSize) return size[find(i)];
            return 0;
        }

        public String toString() {
            return Arrays.toString(arr);
        }
    }

//              /$$     /$$ /$$
//             | $$    |__/| $$
//  /$$   /$$ /$$$$$$   /$$| $$  /$$$$$$$
// | $$  | $$|_  $$_/  | $$| $$ /$$_____/
// | $$  | $$  | $$    | $$| $$|  $$$$$$
// | $$  | $$  | $$ /$$| $$| $$ \____  $$
// |  $$$$$$/  |  $$$$/| $$| $$ /$$$$$$$/
//  \______/    \___/  |__/|__/|_______/


    static void swap(int[] arr, int f, int s) {
        arr[f] ^= arr[s];
        arr[s] ^= arr[f];
        arr[f] ^= arr[s];
    }

    static void swap(long[] arr, int f, int s) {
        arr[f] ^= arr[s];
        arr[s] ^= arr[f];
        arr[f] ^= arr[s];
    }

    static int sign(int x) {
        if (x == 0) return 0;
        return x > 0 ? 1 : - 1;
    }

    static long sign(long x) {
        if (x == 0) return 0;
        return x > 0 ? 1 : - 1;
    }

    static int diff(int a, int b) {
        return abs(a - b);
    }

    static long diff(long a, long b) {
        return abs(a - b);
    }

    static boolean isSqrt(double a) {
        double sr = Math.sqrt(a);
        return ((sr - Math.floor(sr)) == 0);
    }

    static long abs(long a) {
        return Math.abs(a);
    }

    static int abs(int a) {
        return Math.abs(a);
    }
    
    static int min(int x, int y) {
        return Math.min(x, y);
    }

    static long min(long x, long y) {
        return Math.min(x, y);
    }
    
    static int max(int x, int y) {
        return Math.max(x, y);
    }
    
    static long max(long x, long y) {
        return Math.max(x, y);
    }

    static int min(int ... arr) {
        int min = Integer.MAX_VALUE;
        for (int var : arr)
            min = Math.min(min, var);
        return min;
    }

    static long min(long ... arr) {
        long min = Long.MAX_VALUE;
        for (long var : arr)
            min = Math.min(min, var);
        return min;
    }

    static long max(long ... arr) {
        long max = Long.MIN_VALUE;
        for (long var : arr)
            max = Math.max(max, var);
        return max;
    }

    static int max(int... arr) {
        int max = Integer.MIN_VALUE;
        for (int var : arr)
            max = Math.max(max, var);
        return max;
    }

    static long modInverse(long a) {
        long[] g = gcde(a, MODL);
        long x = g[1], y = g[2];
        if (g[0] != 1)
            return 0;
        else {
            // m is added to handle negative x
            return (g[1] % MODL + MODL) % MODL;
        }
    }

    static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    static long[] gcde(long a, long b) {
        // Base Case
        if (a == 0) {
            return new long[] {b, 0, 1};
        }

        long[] gcd = gcde(b % a, a);
        long x1 = gcd[1], y1 = gcd[2]; // To store results of recursive call

        // Update x and y using results of recursive
        // call
        gcd[1] = y1 - (b / a) * x1;
        gcd[2] = x1;

        return gcd;
    }

// ____________________________________________________________________________
//|                                                                            |
//|  /$$$$$$  /$$$$$$         /$$$$$$   /$$                /$$$$$$   /$$$$$$   |
//| |_  $$_/ /$$__  $$       /$$__  $$ | $$               /$$__  $$ /$$__  $$  |
//|   | $$  | $$  \ $$      | $$  \__//$$$$$$   /$$   /$$| $$  \__/| $$  \__/  |
//|   | $$  | $$  | $$      |  $$$$$$|_  $$_/  | $$  | $$| $$$$    | $$$$      |
//|   | $$  | $$  | $$       \____  $$ | $$    | $$  | $$| $$_/    | $$_/      |
//|   | $$  | $$  | $$       /$$  \ $$ | $$ /$$| $$  | $$| $$      | $$        |
//|  /$$$$$$|  $$$$$$/      |  $$$$$$/ |  $$$$/|  $$$$$$/| $$      | $$        |
//| |______/ \______/        \______/   \___/   \______/ |__/      |__/        |
//|____________________________________________________________________________|

    private static boolean HABLA = false;

    private static byte[] scannerByteBuffer = new byte[1024]; // Buffer of Bytes
    private static int scannerIndex;
    private static InputStream scannerIn;
    private static int scannerTotal;
    private static BufferedWriter printerBW;

    private static int next() throws IOException { // Scan method used to scan buf
        if (scannerTotal < 0)
            throw new InputMismatchException();
        if (scannerIndex >= scannerTotal) {
            scannerIndex = 0;
            scannerTotal = scannerIn.read(scannerByteBuffer);
            if (scannerTotal <= 0)
                return -1;
        }
        return scannerByteBuffer[scannerIndex++];
    }

    static int ni() throws IOException {
        int integer = 0;
        int n = next();
        while (isWhiteSpace(n)) // Removing startPointing whitespaces
            n = next();
        int neg = 1;
        if (n == '-') { // If Negative Sign encounters
            neg = -1;
            n = next();
        }
        while (!isWhiteSpace(n)) {
            if (n >= '0' && n <= '9') {
                integer *= 10;
                integer += n - '0';
                n = next();
            } else
                throw new InputMismatchException();
        }
        return neg * integer;
    }

    static long nl() throws IOException {
        long integer = 0;
        int n = next();
        while (isWhiteSpace(n)) // Removing startPointing whitespaces
            n = next();
        int neg = 1;
        if (n == '-') { // If Negative Sign encounters
            neg = -1;
            n = next();
        }
        while (!isWhiteSpace(n)) {
            if (n >= '0' && n <= '9') {
                integer *= 10;
                integer += n - '0';
                n = next();
            } else
                throw new InputMismatchException();
        }
        return neg * integer;
    }

    static String line() throws IOException {
        StringBuilder sb = new StringBuilder();
        int n = next();
        while (isWhiteSpace(n))
            n = next();
        while (!isNewLine(n)) {
            sb.append((char) n);
            n = next();
        }
        return sb.toString();
    }

    private static boolean isNewLine(int n) {
        return n == '\n' || n == '\r' || n == -1;
    }

    private static boolean isWhiteSpace(int n) {
        return n == ' ' || isNewLine(n) || n == '\t';
    }

    static int[] nia(int n) throws Exception {
        if (n < 0)
            throw new Exception("Array size should be non negative");
        int[] array = new int[n];
        for (int i = 0; i < n; i++)
            array[i] = ni();
        return array;
    }

    static int[][] n2dia(int r, int c) throws Exception {
        if (r < 0 || c < 0)
            throw new Exception("Array size should be non negative");
        int[][] array = new int[r][c];
        for (int i = 0; i < r; i++)
            array[i] = nia(c);
        return array;
    }

    static long[] nla(int n) throws Exception {
        if (n < 0)
            throw new Exception("Array size should be non negative");
        long[] array = new long[n];
        for (int i = 0; i < n; i++)
            array[i] = nl();
        return array;
    }

    static float[] nfa(int n) throws Exception {
        if (n < 0)
            throw new Exception("Array size should be non negative");
        float[] array = new float[n];
        for (int i = 0; i < n; i++)
            array[i] = nl();
        return array;
    }

    static double[] nda(int n) throws Exception {
        if (n < 0)
            throw new Exception("Array size should be non negative");
        double[] array = new double[n];
        for (int i = 0; i < n; i++)
            array[i] = nl();
        return array;
    }

    static <T> void print(T ... str) {
        try {
            for (T ele : str)
                printerBW.append(ele.toString());
            if (DEBUG)
                flush();
        } catch (IOException e) {
            System.out.println(e.toString());
        }
    }

    static <T> void println(T ... str) {
        if (str.length == 0) {
            print('\n');
            return;
        }
        for (T ele : str)
            print(ele, '\n');
    }

    static <T> void debugl(T str) throws IOException {
        if (!DEBUG || !HABLA) return;
        if (str == null) {
            printerBW.append("null");
        } else {
            printerBW.append(str.toString());
        }
        flush();
    }

    static void debug() throws IOException {
        if (!DEBUG || !HABLA) return;
        printerBW.append('\n');
        flush();
    }

    static <T> void debug(T str) throws IOException {
        if (!DEBUG || !HABLA) return;
        if (str == null) {
            printerBW.append("null\n");
        } else {
            printerBW.append(str.toString());
            printerBW.append('\n');
        }
        flush();
    }


    static void flush() throws IOException {
        printerBW.flush();
    }

    static void close() {
        try {
            printerBW.close();
        } catch (IOException e) {
            System.out.println(e.toString());
        }
    }
}