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.io.*;

public class G3D {

	public static void main(String[] args) {
		JS scan = new JS();
		int n = scan.nextInt();
		PrintWriter out = new PrintWriter(System.out);
		ArrayList<PointA> p1 = new ArrayList<PointA>();
		ArrayList<Point> p2 = new ArrayList<Point>();
		
		for(int i = 0; i < n; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			if(a < b) p1.add(new PointA(a, b, i+1));
			else p2.add(new Point(a, b, i+1));
		}
		Collections.sort(p1);
		Collections.sort(p2);
		if(p1.size() > p2.size()) {
			out.println(p1.size());
			for(int i = 0; i < p1.size(); i++)
				out.print(p1.get(i).idx+" ");
		}
		else {
			out.println(p2.size());
			for(int i = 0; i < p2.size(); i++)
				out.print(p2.get(i).idx+" ");
		}
		out.flush();
	}
	
	static class Point implements Comparable<Point>{
		
		int a;
		int b;
		int idx;
		
		public Point(int a, int b, int i) {
			this.a = a;
			this.b = b;
			idx = i;
		}

		@Override
		public int compareTo(Point o)
		{
			return this.a-o.a;
		}
	}
	
	static class PointA implements Comparable<PointA>{
		
		int a;
		int b;
		int idx;
		
		public PointA(int a, int b, int i) {
			this.a = a;
			this.b = b;
			idx = i;
		}

		@Override
		public int compareTo(PointA o)
		{
			// TODO Auto-generated method stub
			return o.a-this.a;
		}
	}
	
	static class ST{

		int n;
		int[] lo, hi, max, delta;

		public ST(int y){
			n = y;
			lo = new int[4*n+1];
			hi = new int[4*n+1];
			max = new int[4*n+1];
			delta = new int[4*n+1];
			init(1, 0, n-1);
		}

		public void increment(int a, int b, int val){
			increment(1, a, b, val);
		}

		public int maximum(int a, int b){
			return maximum(1, a, b);
		}

		public void init(int i, int a, int b){
			lo[i] = a;
			hi[i] = b;
			if(a == b) return;
			int m = (a+b)/2;
			init(2*i, a, m);
			init(2*i+1, m+1, b);
		}

		void prop(int i){
			delta[2*i] += delta[i];
			delta[2*i+1] += delta[i];
			delta[i] = 0;
		}

		void update(int i){
			max[i] = Math.max(max[2*i]+delta[2*i], max[2*i+1]+delta[2*i+1]);
		}

		void increment(int i, int a, int b, int val){ //Lazy Propagation Incrementation
			//No cover
			if(b < lo[i] || hi[i] < a){
				return;
			}
			//Full cover
			if(a <= lo[i] && hi[i] <= b){
				delta[i] += val;
				return;
			}
			//Partial cover
			prop(i);
			increment(2*i, a, b, val); //go to left subtree
			increment(2*i+1, a, b, val); //go to right subtree
			update(i);
		}

		int maximum(int i, int a, int b){
			if(b < lo[i] || hi[i] < a){
				return Integer.MIN_VALUE;
			}
			if(a <= lo[i] && hi[i] <= b){
				return max[i]+delta[i];
			}
			prop(i);
			int minLeft = maximum(2*i, a, b);
			int minRight = maximum(2*i+1, a, b);
			update(i);
			return Math.max(minLeft, minRight);
		}
	}

	static class JS{
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public JS() {
			in = new BufferedInputStream(System.in, BS);
		}

		public JS(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}				
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
	}

}