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$.

Difficulty: interview

Starter code:

Solutions:

import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline
mii=lambda:list(map(int,input().split()))

n=int(input())

l1=[]
l2=[]

for i in range(n):
    a,b=mii()
    if a<b:
        l1.append((-a,b,i))
    else:
        l2.append((a,b,i))

if len(l1)>len(l2):
    l1.sort()
    print(len(l1))
    print(" ".join([str(x[2]+1) for x in l1]))
else:
    l2.sort()
    print(len(l2))
    print(" ".join([str(x[2]+1) for x in l2]))


import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)


def main():
    n = I()
    aa = [LI() for _ in range(n)]
    a = []
    b = []
    for i in range(1,n+1):
        c,d = aa[i-1]
        if c < d:
            a.append((c,i))
        else:
            b.append((c,i))

    if len(a) >= len(b):
        a.sort(key=lambda x: -x[0])
        r = a
    else:
        b.sort(key=lambda x: x[0])
        r = b

    return '{}\n{}'.format(len(r),' '.join(map(lambda x: str(x[1]), r)))


print(main())



def solve():
    N = int(input())
    
    incr = []
    decr = []
    
    for i in range(1,N+1):
        a, b = map(int, input().split())
        
        if a > b:
            decr.append((a,b,i))
        else:
            incr.append((a,b,i))
            
    result1 = []
    result2 = []

    if decr:
        decr.sort(key = lambda x:x[1])
        
        result1.append(decr[0])
        
        for i in range(1, len(decr)):
            a, b, idx = decr[i]
            if a > result1[i-1][1]:
                result1.append((a,b,idx))
    
    if incr:
        incr.sort(key = lambda x:x[1])
        incr.reverse()

        result2.append(incr[0])
        
        for i in range(1, len(incr)):
            a, b, idx = incr[i]
            if a < result2[i-1][1]:
                result2.append((a,b,idx))

    if len(result1) > len(result2):
        print (len(result1))
        print (' '.join(str(k[2]) for k in result1))
    else:
        print (len(result2))
        print (' '.join(str(k[2]) for k in result2))
    
def __starting_point():  
    solve()    
__starting_point()

import sys
from bisect import bisect_left
# gcd
# from fractions import gcd
# from math import ceil, floor
# from copy import deepcopy
# from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
# from collections import Counter
# import math
# from functools import reduce
#
# fin = open('in_1.txt', 'r')
# sys.stdin = fin
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


def __starting_point():

    # write code
    n = ii()
    cnta = 0
    cntb = 0
    lista = []
    listb = []
    for i in range(n):
        a, b = mi()
        if a > b:
            cntb += 1
            listb.append((a,b,i+1))
        else:
            cnta += 1
            lista.append((a,b,i+1))
    if cnta >= cntb:
        lista.sort(key=lambda x: x[0],reverse=True)
        print(len(lista))
        for i in lista:
            print(i[2], end=" ")
        print()
    else:
        listb.sort(key=lambda x: x[1])
        print(len(listb))
        for i in listb:
            print(i[2], end=" ")
        print()
__starting_point()

import sys
input = sys.stdin.readline
N = int(input())
X = []
Y = []
for i in range(N):
    a, b = map(int, input().split())
    if a < b:
        X.append((a, b, i+1))
    else:
        Y.append((a, b, i+1))

if len(Y) > len(X):
    X = sorted(Y, key = lambda x: x[0])
else:
    X = sorted(X, key = lambda x: -x[0])

print(len(X))
print(*[x[2] for x in X])

n = int(input())

v = []
u = []
for i in range(n):
	x = input().split(' ')
	a = int(x[0])
	b = int(x[1])
	if a > b:
		v.append((a,b,i + 1))
	else:
		u.append((a,b,i+1))

'''nr = 1
sol = [str(v[0][2])]
act = v[0][1]
i = 1
n = len(v)
while i < n:
	while i < n and v[i][0] < act:
		i += 1
	if i < n:
		nr += 1
		sol.append(str(v[i][2]))
		act = v[i][1]
		i += 1

u = sorted(uv, key = lambda x:x[1])
nr2 = 1
sol2 = [str(u[0][2])]
act = u[0][1]
i = 1
n = len(u)
while i < n:
	while i < n and u[i][0] < act:
		i += 1
	if i < n:
		nr2 += 1
		sol2.append(str(u[i][2]))
		act = u[i][1]
		i += 1'''
if len(u) > len(v):
	u = sorted(u, key = lambda x:x[1], reverse = True)
	print(len(u))
	sol = []
	for i in range(len(u)):
		sol.append(str(u[i][2]))
	print(' '.join(sol))
else:
	v = sorted(v, key = lambda x:x[1], reverse = False)
	print(len(v))
	sol = []
	for i in range(len(v)):
		sol.append(str(v[i][2]))
	print(' '.join(sol))



n=int(input())
l1=[]
l2=[]
for i in range(n):
    a,b=map(int,input().split())
    if a<b:
        l1.append((a,b,i+1))
    else :
        l2.append((b,a,i+1))
l1.sort()
l1=l1[::-1]
l2.sort()
if len(l1)>=len(l2):
    print(len(l1))
    for item in l1:
        print(item[2],end=" ")
else :
    print(len(l2))
    for item in l2:
        print(item[2],end=" ")

n = int(input())
small = []
large = []
idx = {}
for i in range(1, n+1):
    tup = input().split()
    tup[0] = int(tup[0])
    tup[1] = int(tup[1])
    tup = tuple(tup)
    idx[tup] = i
    if tup[0] > tup[1]:
        large.append(tup)
    else:
        small.append(tup)
small_best = False
if len(small) > len(large):
    small_best = True
    small.sort(reverse=True)
else:
    large.sort()
if small_best == True:
    print(len(small))
    for tup in small:
        print(idx[tup], end = " ")
    print()
else:
    print(len(large))
    for tup in large:
        print(idx[tup], end =" ")
    print()


N = int(input())
inc = []
dec = []
for i in range(N):
    a, b = map(int, input().split())
    if a<b: inc.append((a, b, i+1))
    else: dec.append((a, b, i+1))
inc.sort(key=lambda x: x[1], reverse=True)
dec.sort(key=lambda x: x[1])
if len(inc)>=len(dec):
    print(len(inc))
    for i in inc: print(i[2], end=' ')
else:
    print(len(dec))
    for i in dec: print(i[2], end=' ')


def func(i):
	return 0-ar[i][0]
def func2(i):
	return ar[i][0]
n=int(input())
ar=[[0 for x in range(2)] for y in range(n)]
for i in range(n):
	ar[i][0],ar[i][1]=map(int,input().split())
mn=[]
mx=[]
for i in range(n):
	if(ar[i][0]<ar[i][1]):
		mn.append(i)
	else:
		mx.append(i)
if(len(mn)>len(mx)):
	mn=sorted(mn, key = func)
	print(len(mn))
	for x in mn:
		print (x+1,end=" ")
else:
	# mx=sorted(mx,reverse=True)
	mx=sorted(mx, key = func2)
	print(len(mx))
	for x in mx:
		print (x+1,end=" ")


n=int(input())
p=[tuple(int(x) for x in input().split()) for _ in range(n)]
# print(p)
asc = [(x[0], i) for i, x in enumerate(p) if x[0] > x[1]]
desc = [(x[0], i) for i, x in enumerate(p) if x[0] < x[1]]
asc.sort()
desc.sort(reverse=True)
if len(asc) >= len(desc):
    print(len(asc))
    print(' '.join(str(x[1]+1) for x in asc))
else:
    print(len(desc))
    print(' '.join(str(x[1]+1) for x in desc))


n = int(input())
a = list()
f = []
for i in range(n):
    cur = [list(map(int, input().split())), i + 1]
    if cur[0][0] < cur[0][1]:
        f.append(cur)
    else:
        a.append(cur)
if len(f) >= n // 2:
    f.sort(key=lambda x: x[0][0], reverse=True)
    print(len(f))
    ans = ''
    for i in f:
        ans += str(i[1]) + ' '
    print(ans)
else:
    a.sort(key=lambda x: x[0][0], reverse=False)
    print(len(a))
    ans = ''
    for i in a:
        ans += str(i[1]) + ' '
    print(ans)


def seq1(diff,nums):
    index = diff[0][1]
    a,b = nums[index][0],nums[index][1]
    if b > a:
        indices = [index]
    else:
        return []
    x1,x2 = a,b
    for i in range(1,len(diff)):
        index = diff[i][1]
        a,b = nums[index][0],nums[index][1]
        #print(a,b,x2)
        if x2 > a and a < b:
            indices.append(index)
            x2 = b
        else:
            break
        #print(a,b,x2)
    
    return indices

def seq2(diff,nums):
    #print(nums)
    index = diff[0][1]
    a,b = nums[index][0],nums[index][1]
    if b < a:
        indices = [index]
    else:
        return []
    x1,x2 = a,b
    for i in range(1,len(diff)):
        index = diff[i][1]
        a,b = nums[index][0],nums[index][1]
        #print(a,b,x2)
        if a > x2 and a > b:
            indices.append(index)
            x2 = b
        else:
            break

    return indices

def main():
    n = int(input())
    nums = []
    diff1 = []
    diff2 = []
    for i in range(n):
        a,b = map(int,input().split())
        nums.append((a,b))
        if b-a > 0:
            diff1.append((b,i))
        else:
            diff2.append((a,i))

    diff1.sort(reverse = True)
    diff2.sort()
    if diff1:
        ans1 = seq1(diff1,nums)
    else:
        ans1 = []
    if diff2:
        ans2 = seq2(diff2,nums)
    else:
        ans2 = []

    if len(ans1) >= len(ans2):
        print(len(ans1))
        for i in ans1:
            print(i+1,end = ' ')
    else:
        print(len(ans2))
        for i in ans2:
            print(i+1,end = ' ')

main()


# https://codeforces.com/contest/1148/problem/D
n = int(input())

d = {}
d['+'] = []
d['-'] = []

for _ in range(n):
    a, b = list(map(int, input().split()))
    if a < b:
        d['+'].append([b, _])
    else:
        d['-'].append([b, _])
        
d['+'] = sorted(d['+'], key = lambda x: x[0], reverse=True)
d['-'] = sorted(d['-'], key = lambda x: x[0])

s = ''
if len(d['+']) > len(d['-']):
    print(len(d['+']))
    for x in d['+']:
        s+=str(x[1]+1) +  ' '
else:
    print(len(d['-']))
    for x in d['-']:
        s+=str(x[1]+1) +  ' '
        
print(s)

#5
#1 7
#6 4
#2 10
#9 8
#3 5


# from bisect import bisect_left
import sys

def solve(a, cmp):
    # if not a:
    #     return []
    # print(up)
    res = [-1 for _ in a]
    ptr = 0
    for id, e in enumerate(a):
        if ptr == 0 or cmp(a[res[ptr - 1]][0][1], e[0][0]):
            res[ptr] = id
            ptr += 1
    return [a[res[id]][1] for id in range(ptr)]


n = int(input())
a = [tuple(int(e) for e in line.split()) for line in sys.stdin]

up = [(e, id) for id, e in enumerate(a) if e[0] < e[1]]
down = [(e, id) for id, e in enumerate(a) if e[0] > e[1]]


up.sort(key=lambda e: -e[0][1])
down.sort(key=lambda e: e[0][1])

res = solve(up, lambda a, b: a > b)
res_down = solve(down, lambda a, b: a < b)

if len(res) < len(res_down):
    res = res_down

print(len(res))
print(" ".join(str(_ + 1) for _ in res))

# from bisect import bisect_left
import sys

def solve(a, cmp):
    # if not a:
    #     return []
    # print(up)
    res = [-1 for _ in a]
    ptr = 0
    for id, e in enumerate(a):
        if ptr == 0 or cmp(a[res[ptr - 1]][0][1], e[0][0]):
            res[ptr] = id
            ptr += 1
    return [a[res[id]][1] for id in range(ptr)]


n = int(input())
a = [tuple(int(e) for e in line.split()) for line in sys.stdin]

up = [(e, id) for id, e in enumerate(a) if e[0] < e[1]]
down = [(e, id) for id, e in enumerate(a) if e[0] > e[1]]


up.sort(key=lambda e: -e[0][1])
down.sort(key=lambda e: e[0][1])

res = solve(up, lambda a, b: a > b)
res_down = solve(down, lambda a, b: a < b)

if len(res) < len(res_down):
    res = res_down

print(len(res))
print(" ".join(str(_ + 1) for _ in res))


import sys
import functools
commands = []

def less_int(x, y):
    return x[0] - y[0]
    
def more_int(x, y):
    return y[0] - x[0]

n = int(input())
ab = []
ba = []
for i in range(n):
    a_s  = list(map(int,input().split(' ')))
    if a_s[0] > a_s[1]:
        ab.append((a_s[0], a_s[1], i + 1))
    else:
        ba.append((a_s[0], a_s[1], i + 1))
ab.sort(key=functools.cmp_to_key(less_int))
ba.sort(key=functools.cmp_to_key(more_int))

answ = ab
if len(ba) > len(ab):
    answ = ba
print(len(answ))
for a,b,c in answ:
    print(c, end=' ')





n = int(input())
D = []
U = []
for i in range(n):
    a, b = list(map(int, input().split()))
    if a < b:
        U.append((a, b, i + 1))
    else:
        D.append((a, b, i + 1))

if len(U) <= len(D):
    D = sorted(D, key=lambda x: x[0])
    ans = []
    for i in range(len(D)):
        ans.append(D[i][2])
else:
    U = sorted(U, key=lambda x: -x[0])
    ans = []
    for i in range(len(U)):
        ans.append(U[i][2])

print(len(ans))
print(*ans)


from sys import stdin
n=int(stdin.readline().strip())

s=[list(map(int,stdin.readline().strip().split())) for i in range(n)]
s1=[]
s2=[]
for i in range(n):
    if s[i][0]>s[i][1]:
        s1.append(s[i][::-1]+[i])
    if s[i][0]<s[i][1]:
        s2.append(s[i][::-1]+[i])
s1.sort()
s2.sort(reverse=True)
ans1=[]
ans2=[]
if len(s1)>0:
    ans1=[s1[0]]
if len(s2)>0:
    ans2=[s2[0]]
for i in range(len(s1)):
    if ans1[-1][0]<s1[i][0]:
        ans1.append(s1[i])
for i in range(len(s2)):
    if ans2[-1][0]>s2[i][0]:
        ans2.append(s2[i])
if len(ans1)>len(ans2):
    r=[]
    for i in ans1:
        r.append(i[2]+1)
    print(len(r))
    print(*r)
else:
    r=[]
    for i in ans2:
        r.append(i[2]+1)
    print(len(r))
    print(*r)


#from hypothesis import given
#from hypothesis.strategies import permutations, integers


def solve(n, p):
    i_p = list(enumerate(p))
    i_p.sort(key=lambda i_ab: (i_ab[1][1], i_ab[1][0], i_ab[0]))
    zig = list(reversed([i for i, (a, b) in i_p if a < b]))
    #print([(i, p[i]) for i in zig])
    for i in range(len(zig) - 1):
        assert p[zig[i]][1] > p[zig[i + 1]][0]
    for i in zig:
        assert p[i][0] < p[i][1]
    zag = [i for i, (a, b) in i_p if a > b]
    #print([(i, p[i]) for i in zag])
    for i in range(len(zag) - 1):
        assert p[zag[i]][1] < p[zag[i + 1]][0]
    for i in zag:
        assert p[i][0] > p[i][1]
    if len(zig) < len(zag):
        return zag
    return zig


# IDK why generation is so slow for this.
#@given(integers(min_value=2, max_value=int(1e2))
#    .flatmap(lambda n: permutations(range(1, 2*n + 1)))
#    .map(lambda ab: [(ab[i], ab[i + 1]) for i in range(0, len(ab), 2)]))
#def test_solve(p):
#    solve(len(p), p)


def main():
    n = int(input())
    p = [None]*n
    for i in range(n):
        p[i] = tuple(map(int, input().split()))
    i = solve(n, p)
    print(len(i))
    print(*[ix + 1 for ix in i])


def __starting_point():
    main()

__starting_point()

n=int(input())
mn,mx=[],[]
for i in range(n):
    b=list(map(int,input().split()))
    if(b[0]>b[1]):
        mx.append(b+[i+1])
    else:mn.append(b+[i+1])
if len(mx)>len(mn):
    ans=sorted(mx)
else:
    ans=sorted(mn,reverse=True)
print(len(ans))
print(*[x[2] for x in ans])

n = int(input())
b = []
mx = []
mn = []
mx_i = []
mn_i = []
for i in range(n):
    u,v = [int(x) for x in input().strip().split()]
    # b.append((u,v))
    if u>v:
        mx.append((u,v))
        mx_i.append(i+1)
    else:
        mn.append((u,v))
        mn_i.append(i+1)
if len(mx)>len(mn):
    print(len(mx))
    res = [ x[1] for x in sorted(zip(mx,mx_i))]
else:
    print(len(mn))
    res = [ x[1] for x in sorted(zip(mn,mn_i), reverse=True)]

for r in res:
    print(r, end=" ")
print()   


from sys import stdin
from bisect import bisect_left as bl
input=stdin.readline
n=int(input())
a=[]
b=[]
for i in range(n):
    c,d=map(int,input().split())
    if c<d:
        a.append([d,i])
    else:
        b.append([c,i])
a.sort(reverse=True)
b.sort()
if len(a)>len(b):
    print(len(a))
    for i in a:
        print(i[1]+1,end=' ')
else:
    print(len(b))
    for i in b:
        print(i[1]+1,end=' ')