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:
//package que_b;

import java.io.*;
import java.util.*;
import java.math.*;

public class utkarsh {

    InputStream is;
    PrintWriter out;
    
    long mod = (long)(1e9 + 7), inf = (long)(3e18);
    
    class pair {
        int F, S, I;
        pair(int f, int s, int i) {
            F = f;  S = s;  I = i;
        }
    }
    
    ArrayList <Integer> one(ArrayList <pair> a) {
        if(a.isEmpty()) return new ArrayList<>();
        Collections.sort(a, (pair u, pair v) -> (u.F - v.F));
        int n = a.size();
        int dp[] = new int[n];
        int pt[] = new int[n];
        Stack <Integer> st = new Stack<>();
        for(int i = 0; i < n; i++) {
            while(!st.isEmpty() && a.get(st.peek()).S < a.get(i).F) st.pop();
            if(st.isEmpty()) {
                dp[i] = 1;
                pt[i] = -1;
            } else {
                dp[i] = 1 + dp[st.peek()];
                pt[i] = st.peek();
            }
            st.push(i);
        }
        int m = 0;
        for(int i = 1; i < n; i++)  if(dp[i] > dp[m])   m = i;
        st.clear();
        while(m != -1) {
            st.push(m);
            m = pt[m];
        }
        ArrayList <Integer> ans = new ArrayList<>();
        while(!st.isEmpty())    ans.add(a.get(st.pop()).I);
        return ans;
    }
    
    ArrayList <Integer> two(ArrayList <pair> b) {
        if(b.isEmpty()) return new ArrayList<>();
        Collections.sort(b, (pair u, pair v) -> (v.F - u.F));
        int n = b.size();
        int dp[] = new int[n];
        int pt[] = new int[n];
        Stack <Integer> st = new Stack<>();
        for(int i = 0; i < n; i++) {
            while(!st.isEmpty() && b.get(st.peek()).S > b.get(i).F) st.pop();
            if(st.isEmpty()) {
                dp[i] = 1;
                pt[i] = -1;
            } else {
                dp[i] = 1 + dp[st.peek()];
                pt[i] = st.peek();
            }
            st.push(i);
        }
        int m = 0;
        for(int i = 1; i < n; i++)  if(dp[i] > dp[m])   m = i;
        st.clear();
        while(m != -1) {
            st.push(m);
            m = pt[m];
        }
        ArrayList <Integer> ans = new ArrayList<>();
        while(!st.isEmpty())    ans.add(b.get(st.pop()).I);
        return ans;
    }
    
    void solve() {
        int n = ni();
        ArrayList <pair> a = new ArrayList<>();
        ArrayList <pair> b = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            int u = ni(), v = ni();
            if(u < v)   a.add(new pair(u, v, i+1));
            else        b.add(new pair(u, v, i+1));
        }
        if(a.size() >= b.size()) {
            Collections.sort(a, (pair u, pair v) -> (v.S - u.S));
            out.println(a.size());
            for(pair p : a)  out.print(p.I +" ");
        } else {
            Collections.sort(b, (pair u, pair v) -> (u.S - v.S));
            out.println(b.size());
            for(pair p : b)  out.print(p.I +" ");
        }
    }

    long mp(long b, long e, long mod) {
        b %= mod;
        long r = 1;
        while(e > 0) {
            if((e & 1) == 1) {
                r *= b; r %= mod;
            }
            b *= b; b %= mod;
            e >>= 1;
        }
        return r;
    }

    //---------- I/O Template ----------
    
    public static void main(String[] args) { new utkarsh().run(); }
    void run() { 
        is = System.in; 
        out = new PrintWriter(System.out);
        solve();
        out.flush();
    }
    
    byte input[] = new byte[1024];
    int len = 0, ptr = 0;
    
    int readByte() { 
        if(ptr >= len) { ptr = 0; 
            try { len = is.read(input); } 
            catch(IOException e) { throw new InputMismatchException(); } 
            if(len <= 0) { return -1; } 
        } return input[ptr++];
    }
    boolean isSpaceChar(int c) { return !( c >= 33 && c <= 126 ); }
    int skip() { 
        int b = readByte(); 
        while(b != -1 && isSpaceChar(b)) { b = readByte(); } 
        return b;
    }
    
    char nc() { return (char)skip(); }
    String ns() { 
        int b = skip(); 
        StringBuilder sb = new StringBuilder(); 
        while(!isSpaceChar(b)) { sb.appendCodePoint(b); b = readByte(); } 
        return sb.toString();
    }
    String nLine() { 
        int b = skip(); 
        StringBuilder sb = new StringBuilder(); 
        while( !(isSpaceChar(b) && b != ' ') ) { sb.appendCodePoint(b); b = readByte(); } 
        return sb.toString();
    }
    int ni() { 
        int n = 0, b = readByte(); 
        boolean minus = false; 
        while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')) { b = readByte(); } 
        if(b == '-') { minus = true; b = readByte(); } 
        if(b == -1) { return -1; }  //no input 
        while(b >= '0' && b <= '9') { n = n * 10 + (b - '0'); b = readByte(); } 
        return minus ? -n : n;
    }
    long nl() { 
        long n = 0L;    int b = readByte(); 
        boolean minus = false; 
        while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')) { b = readByte(); } 
        if(b == '-') { minus = true; b = readByte(); } 
        while(b >= '0' && b <= '9') { n = n * 10 + (b - '0'); b = readByte(); } 
        return minus ? -n : n;
    }

    double nd() { return Double.parseDouble(ns()); }
    float nf() { return Float.parseFloat(ns()); }
    int[] na(int n) { 
        int a[] = new int[n]; 
        for(int i = 0; i < n; i++) { a[i] = ni(); } 
        return a;
    }
    char[] ns(int n) { 
        char c[] = new char[n]; 
        int i, b = skip(); 
        for(i = 0; i < n; i++) { 
            if(isSpaceChar(b)) { break; } 
            c[i] = (char)b; b = readByte(); 
        } return i == n ? c : Arrays.copyOf(c,i);
    }
}