Petya loves football very much, especially when his parents aren't home. Each morning he comes to the yard, gathers his friends and they play all day. From time to time they have a break to have some food or do some chores (for example, water the flowers).

The key in football is to divide into teams fairly before the game begins. There are n boys playing football in the yard (including Petya), each boy's football playing skill is expressed with a non-negative characteristic ai (the larger it is, the better the boy plays). 

Let's denote the number of players in the first team as x, the number of players in the second team as y, the individual numbers of boys who play for the first team as pi and the individual numbers of boys who play for the second team as qi. Division n boys into two teams is considered fair if three conditions are fulfilled:

  * Each boy plays for exactly one team (x + y = n). 
  * The sizes of teams differ in no more than one (|x - y| ≤ 1). 
  * The total football playing skills for two teams differ in no more than by the value of skill the best player in the yard has. More formally: <image>



Your task is to help guys divide into two teams fairly. It is guaranteed that a fair division into two teams always exists.

Input

The first line contains the only integer n (2 ≤ n ≤ 105) which represents the number of guys in the yard. The next line contains n positive space-separated integers, ai (1 ≤ ai ≤ 104), the i-th number represents the i-th boy's playing skills. 

Output

On the first line print an integer x — the number of boys playing for the first team. On the second line print x integers — the individual numbers of boys playing for the first team. On the third line print an integer y — the number of boys playing for the second team, on the fourth line print y integers — the individual numbers of boys playing for the second team. Don't forget that you should fulfil all three conditions: x + y = n, |x - y| ≤ 1, and the condition that limits the total skills.

If there are multiple ways to solve the problem, print any of them.

The boys are numbered starting from one in the order in which their skills are given in the input data. You are allowed to print individual numbers of boys who belong to the same team in any order.

Examples

Input

3
1 2 1


Output

2
1 2 
1
3 


Input

5
2 3 3 1 1


Output

3
4 1 3 
2
5 2 

Note

Let's consider the first sample test. There we send the first and the second boy to the first team and the third boy to the second team. Let's check all three conditions of a fair division. The first limitation is fulfilled (all boys play), the second limitation on the sizes of groups (|2 - 1| = 1 ≤ 1) is fulfilled, the third limitation on the difference in skills ((2 + 1) - (1) = 2 ≤ 2) is fulfilled.

Source: codeforces | Difficulty: MEDIUM
Tags: Sorting

Mathematics

Greedy algorithms


Solutions:
import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def count1(s):
	c = 0
	for i in s:
		if i == '1':
			c += 1
	return c

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True
n = int(input())
l = list(map(int, input().split()))
pos = []
for i in range(0, n):
	pos.append([l[i], i + 1])
pos.sort()
t1 = []
t2 = []
for i in range(0, n):
	if i % 2 == 0:
		t1.append(pos[i][1])
	else:
		t2.append(pos[i][1])
print(len(t1))
print(*t1)
print(len(t2))
print(*t2)


n = int(input())
a = sorted([[int(j), i + 1] for (i, j) in enumerate(input().split())])
s = len(a[::2])
print(s, *[i[1] for i in a[::2]])
print(n - s, *[i[1] for i in a[1::2]])


from __future__ import division, print_function
import math
import os
import sys
from fractions import *
from sys import *
from decimal import *
from io import BytesIO, IOBase
from itertools import *
from collections import *
M = 10 ** 9 + 7
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def inpu():
	return int(inp())

def regularbracket(t):
	p = 0
	for i in t:
		if i == '(':
			p += 1
		else:
			p -= 1
		if p < 0:
			return False
	else:
		if p > 0:
			return False
		else:
			return True

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def reverse1(string):
	pp = ''
	for i in string[::-1]:
		pp += i
	if pp == string:
		return True
	return False

def reverse2(list1):
	l = []
	for i in list1[::-1]:
		l.append(i)
	if l == list1:
		return True
	return False

def mex(list1):
	p = max(list1) + 1
	for i in range(len(list1)):
		if list1[i] != i:
			p = i
			break
	return p

def sumofdigits(n):
	n = str(n)
	s1 = 0
	for i in n:
		s1 += int(i)
	return s1

def perfect_square(n):
	s = math.sqrt(n)
	if s == int(s):
		return True
	return False

def roman_number(x):
	if x > 15999:
		return
	value = [5000, 4000, 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
	symbol = ['F', 'MF', 'M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I']
	roman = ''
	i = 0
	while x > 0:
		div = x // value[i]
		x = x % value[i]
		while div:
			roman += symbol[i]
			div -= 1
		i += 1
	return roman

def soretd(s):
	for i in range(1, len(s)):
		if s[i - 1] > s[i]:
			return False
	return True

def countRhombi(h, w):
	ct = 0
	for i in range(2, h + 1, 2):
		for j in range(2, w + 1, 2):
			ct += (h - i + 1) * (w - j + 1)
	return ct

def countrhombi2(h, w):
	return h * h // 4 * (w * w // 4)

def binpow(a, b):
	if b == 0:
		return 1
	else:
		res = binpow(a, b // 2)
	if b % 2 != 0:
		return res * res * a
	else:
		return res * res

def binpowmodulus(a, b, m):
	a %= m
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b >>= 1
	return res

def coprime_to_n(n):
	result = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
			result -= result // i
		i += 1
	if n > 1:
		result -= result // n
	return result

def prime(x):
	if x == 1:
		return False
	else:
		for i in range(2, int(math.sqrt(x)) + 1):
			if x % i == 0:
				return False
		else:
			return True

def luckynumwithequalnumberoffourandseven(x, n, a):
	if x >= n and str(x).count('4') == str(x).count('7'):
		a.append(x)
	elif x < 1000000000000.0:
		luckynumwithequalnumberoffourandseven(x * 10 + 4, n, a)
		luckynumwithequalnumberoffourandseven(x * 10 + 7, n, a)
	return a

def luckynuber(x, n, a):
	p = set(str(x))
	if len(p) <= 2:
		a.append(x)
	if x < n:
		luckynuber(x + 1, n, a)
	return a

def interact(type, x):
	if type == 'r':
		inp = input()
		return inp.strip()
	else:
		print(x, flush=True)

def findTrailingZeros(n):
	count = 0
	while n >= 5:
		n //= 5
		count += n
	return count

def mergeSort(arr):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergeSort(L)
		mergeSort(R)
		i = j = k = 0
		while i < len(L) and j < len(R):
			if L[i] < R[j]:
				arr[k] = L[i]
				i += 1
			else:
				arr[k] = R[j]
				j += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1
res = set()

def solven(p, l, a, b, n):
	if p > n or l > 10:
		return
	if p > 0:
		res.add(p)
	solven(p * 10 + a, l + 1, a, b, n)
	solven(p * 10 + b, l + 1, a, b, n)

def subsetsUtil(A, subset, index, d):
	print(*subset)
	s = sum(subset)
	d.append(s)
	for i in range(index, len(A)):
		subset.append(A[i])
		subsetsUtil(A, subset, i + 1, d)
		subset.pop(-1)
	return d

def subsetSums(arr, l, r, d, sum=0):
	if l > r:
		d.append(sum)
		return
	subsetSums(arr, l + 1, r, d, sum + arr[l])
	subsetSums(arr, l + 1, r, d, sum)
	return d

def print_factors(x):
	factors = []
	for i in range(1, x + 1):
		if x % i == 0:
			factors.append(i)
	return factors

def calc(X, d, ans, D):
	if len(X) == 0:
		return
	i = X.index(max(X))
	ans[D[max(X)]] = d
	Y = X[:i]
	Z = X[i + 1:]
	calc(Y, d + 1, ans, D)
	calc(Z, d + 1, ans, D)

def factorization(n, l):
	c = n
	if prime(n) == True:
		l.append(n)
		return l
	for i in range(2, c):
		if n == 1:
			break
		while n % i == 0:
			l.append(i)
			n = n // i
	return l

def good(b):
	l = []
	i = 0
	while len(b) != 0:
		if b[i] < b[len(b) - 1 - i]:
			l.append(b[i])
			b.remove(b[i])
		else:
			l.append(b[len(b) - 1 - i])
			b.remove(b[len(b) - 1 - i])
	if l == sorted(l):
		return True
	return False

def generate(st, s):
	if len(s) == 0:
		return
	if s not in st:
		st.add(s)
		for i in range(len(s)):
			t = list(s).copy()
			t.remove(s[i])
			t = ''.join(t)
			generate(st, t)
	return

def largestincreasingsubsequence(A):
	l = [1] * len(A)
	sub = []
	for i in range(1, len(l)):
		for k in range(i):
			if A[k] < A[i]:
				sub.append(l[k])
		l[i] = 1 + max(sub, default=0)
	return max(l, default=0)

def findOR(nums, N):
	prefix_sum = 0
	result = 0
	for i in range(N):
		result |= nums[i]
		prefix_sum += nums[i]
		result |= prefix_sum
	return result

def OR(a, n):
	ans = a[0]
	for i in range(1, n):
		ans |= a[i]
	return ans

def main():
	n = inpu()
	arr = lis()
	l = []
	p = []
	q = []
	for i in range(len(arr)):
		q.append([arr[i], i + 1])
	q.sort()
	for i in range(0, n, 2):
		l.append(q[i][1])
	for i in range(1, n, 2):
		p.append(q[i][1])
	print(len(l))
	print(*l)
	print(len(p))
	print(*p)
main()


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass
n = L()[0]
A = L()
Z = [[A[i], i + 1] for i in range(n)]
Z.sort()
x = []
y = []
sx = 0
sy = 0
for i in range(n):
	if sx > sy:
		y.append(Z[i][1])
		sy += Z[i][0]
	else:
		x.append(Z[i][1])
		sx += Z[i][0]
print(len(x))
print(*x)
print(len(y))
print(*y)
endtime = time.time()


class Player:

	def __init__(self, position, skill):
		self.position = position
		self.skill = skill
n = int(input())
players = [Player(i + 1, x) for (i, x) in enumerate(map(int, input().split()))]
players.sort(key=lambda player: player.skill)
(left, right) = ([], [])
for (i, player) in enumerate(players):
	if i % 2 == 0:
		left.append(player.position)
	else:
		right.append(player.position)
print(len(left))
print(' '.join(map(str, left)))
print(len(right))
print(' '.join(map(str, right)))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
arr = [[int(num) + 1, int(skill)] for (num, skill) in enumerate(input().split())]
x = []
y = []
arr.sort(key=lambda x: x[1])
if n % 2 == 0:
	while arr:
		x.append(arr.pop()[0])
		y.append(arr.pop()[0])
else:
	last = arr.pop()[0]
	sumx = 0
	sumy = 0
	while arr:
		sumx += arr[-1][1]
		x.append(arr.pop()[0])
		sumy += arr[-1][1]
		y.append(arr.pop()[0])
	if sumx < sumy:
		x.append(last)
	else:
		y.append(last)
print(len(x))
print(*x)
print(len(y))
print(*y)


n = int(input())
x = list(map(int, input().split()))
a = []
for i in range(n):
	a.append([x[i], i + 1])
a.sort()
turn = 0
p = []
q = []
for i in range(n - 1, -1, -1):
	if turn:
		p.append(a[i][1])
	else:
		q.append(a[i][1])
	turn = 1 - turn
print(len(p))
print(*p)
print(len(q))
print(*q)


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	players = [None] * n
	i = 0
	for skill in input().split():
		players[i] = (int(skill), i)
		i += 1
	players.sort()
	teams = [[], []]
	accumulatedSkills = [0, 0]
	current = 0
	for i in range(n):
		if i == n - 1 and n & 1:
			if accumulatedSkills[0] < accumulatedSkills[1]:
				current = 0
			else:
				current = 1
		teams[current].append(str(players[i][1] + 1))
		accumulatedSkills[current] += players[i][0]
		current = 1 - current
	for team in teams:
		print(len(team))
		print(' '.join(team))
BUFFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
input = lambda : sys.stdin.readline().rstrip('\r\n')

def print(*args, **kwargs):
	sep = kwargs.pop('sep', ' ')
	file = kwargs.pop('file', sys.stdout)
	atStart = True
	for x in args:
		if not atStart:
			file.write(sep)
		file.write(str(x))
		atStart = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
main()


import sys
sys.setrecursionlimit(1000000)

def solve():
	(n,) = rv()
	(ainput,) = rl(1)
	a = [(val, i) for (i, val) in enumerate(ainput)]
	a.sort()
	a = a[::-1]
	(f, s) = (list(), list())
	for i in range(len(a)):
		if i % 2 == 0:
			f.append(a[i][1] + 1)
		else:
			s.append(a[i][1] + 1)
	print(len(f))
	print(' '.join(map(str, f)))
	print(len(s))
	print(' '.join(map(str, s)))

def rv():
	return map(int, input().split())

def rl(n):
	return [list(map(int, input().split())) for _ in range(n)]
if sys.hexversion == 50594544:
	sys.stdin = open('test.txt')
solve()


n = int(input())
a = list(map(int, input().split()))
l = []
for i in range(n):
	l.append([a[i], i + 1])
l = sorted(l, key=lambda h: -1 * h[0])
a = []
b = []
for i in range(n):
	if i % 2 == 0:
		a.append(l[i][1])
	else:
		b.append(l[i][1])
print(len(a))
print(*a)
print(len(b))
print(*b)


n = int(input())
l = [(i, num + 1) for (num, i) in enumerate([int(j) for j in input().split()])]
t1 = []
t2 = []
for (ind, (_, num)) in enumerate(sorted(l)):
	if ind % 2 == 0:
		t1.append(num)
	else:
		t2.append(num)
print(len(t1))
for i in sorted(t1):
	print(i, end=' ')
print()
print(len(t2))
for i in sorted(t2):
	print(i, end=' ')


import sys
from math import log2, floor, ceil, sqrt, gcd
import bisect
sys.setrecursionlimit(10 ** 5)
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 1000000007
n = int(ri())
arr = Ri()
maxx = max(arr)
arr = [[arr[i], i] for i in range(len(arr))]
arr.sort(key=lambda x: x[0])
a = []
b = []
asum = 0
bsum = 0
turn = 0
for i in range(n // 2):
	if turn == 0:
		a.append(arr[i])
		a.append(arr[n - i - 1])
		asum += arr[i][0]
		asum += arr[n - i - 1][0]
	else:
		b.append(arr[i])
		b.append(arr[n - i - 1])
		bsum += arr[i][0]
		bsum += arr[n - i - 1][0]
	turn ^= 1
if n % 2 != 0:
	if asum < bsum:
		asum += arr[n // 2][0]
		a.append(arr[n // 2])
	else:
		bsum += arr[n // 2][0]
		b.append(arr[n // 2])
a.sort(key=lambda x: x[0])
b.sort(key=lambda x: x[0])
while abs(asum - bsum) > maxx or abs(len(a) - len(b)) > 1:
	if asum > bsum and len(a) >= len(b):
		val = a.pop()
		asum -= val[0]
		bsum += val[0]
		b.append(val)
	elif bsum > asum and len(a) <= len(b):
		val = b.pop()
		bsum -= val[0]
		asum += val[0]
		a.append(val)
print(len(a))
print(*[a[i][1] + 1 for i in range(len(a))])
print(len(b))
print(*[b[i][1] + 1 for i in range(len(b))])


n = int(input())
arr = list(map(int, input().split()))
idx = [i for i in range(n)]
idx.sort(key=lambda i: arr[i])
print(n // 2)
for i in range(n // 2):
	print(idx[2 * i + 1] + 1, end=' ')
print()
print(n - n // 2)
for i in range(n - n // 2):
	print(idx[2 * i] + 1, end=' ')
print()


from sys import stdin

def arr_enu():
	return sorted([[i + 1, int(x)] for (i, x) in enumerate(stdin.readline().split())], key=lambda x: x[1])
(n, a, team1, team2) = (int(input()), arr_enu(), [], [])
for i in range(n):
	if i % 2:
		team1.append(a[i][0])
	else:
		team2.append(a[i][0])
print(len(team1))
print(*team1)
print(len(team2))
print(*team2)


n = int(input())
a = list(map(int, input().split()))
all = []
for i in range(n):
	all.append([a[i], i + 1])
all.sort(key=lambda x: x[0])
team_1 = []
team_2 = []
for i in range(n):
	if i % 2 == 0:
		team_1.append(all[i][1])
	else:
		team_2.append(all[i][1])
print(len(team_1))
print(*team_1)
print(len(team_2))
print(*team_2)


import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(95000)

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()
n = int(input())
arr = [int(x) for x in input().split()]
for i in range(n):
	arr[i] = [arr[i], i + 1]
arr = sorted(arr, key=lambda x: x[0])
(i, j) = (0, n - 1)
f = 1
(ans1, ans2) = ([], [])
while i <= j:
	if f == 1:
		if i < j:
			ans1.append(arr[i])
			ans1.append(arr[j])
		else:
			ans1.append(arr[i])
		f = 0
	else:
		if i < j:
			ans2.append(arr[i])
			ans2.append(arr[j])
		else:
			ans2.append(arr[i])
		f = 1
	i += 1
	j -= 1
if f == 0 and n % 2 == 0:
	ans2.append(ans1.pop())
print(len(ans1))
for ele in ans1:
	print(ele[1], end=' ')
print()
print(len(ans2))
for ele in ans2:
	print(ele[1], end=' ')
print()


n = int(input())
a = list(map(int, input().split()))
a = [(a[i], i + 1) for i in range(n)]
a.sort()
lp = [a[x][1] for x in range(0, n, 2)]
rp = [a[x][1] for x in range(1, n, 2)]
print(len(lp))
print(*lp)
print(len(rp))
print(*rp)


import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

def In():
	return map(int, sys.stdin.readline().split())

def Sn():
	return sys.stdin.readline().strip()

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def main():
	try:
		n = I()
		l = list(enumerate(list(In())))
		l.sort(key=lambda x: x[1])
		(a, b) = ([], [])
		q = 0
		for i in range(n - 1, -1, -2):
			if q == 0:
				a.append(l[i][0])
				b.append(l[i - 1][0])
				q = 1
			else:
				q = 0
				a.append(l[i - 1][0])
				b.append(l[i][0])
			if i - 2 < 1:
				break
		if n & 1:
			if q:
				b.append(l[0][0])
			else:
				a.append(l[0][0])
		print(len(a))
		for x in a:
			print(x + 1, end=' ')
		print()
		print(len(b))
		for x in b:
			print(x + 1, end=' ')
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(1):
	main()


import os
import sys
import math
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
a = list(map(int, input().split()))
b = list()
for i in range(n):
	b.append((a[i], i + 1))
b.sort()
c = (n + 1) // 2
c1 = list()
print(c)
for i in range(0, n, 2):
	c1.append(b[i][1])
print(*c1)
c = n // 2
c2 = list()
print(c)
for i in range(1, n, 2):
	c2.append(b[i][1])
print(*c2)


from sys import stdin
import sys
import copy
sys.setrecursionlimit(15000)
n = int(stdin.readline().strip())
arr = list(map(int, stdin.readline().split()))
for i in range(len(arr)):
	arr[i] = [i, arr[i]]
arr = sorted(arr, key=lambda x: x[1])
first = []
second = []
for i in range(len(arr)):
	if i % 2:
		first.append(arr[i][0] + 1)
	else:
		second.append(arr[i][0] + 1)
print(len(first))
print(*first)
print(len(second))
print(*second)


from sys import stdin, stdout
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
for _ in range(1):
	n = nmbr()
	a = sorted(zip(lst(), range(1, 1 + n)), reverse=1)
	team1 = []
	team2 = []
	for i in range(n):
		if i & 1:
			team1 += [a[i][1]]
		else:
			team2 += [a[i][1]]
	print(len(team1))
	print(*team1)
	print(len(team2))
	print(*team2)


def team(arr):
	base = [[arr[i], i + 1] for i in range(len(arr))]
	base = sorted(base, key=lambda s: s[0], reverse=True)
	t1 = []
	t2 = []
	while base:
		t1.append(base[0][1])
		base.pop(0)
		if base:
			t2.append(base[0][1])
			base.pop(0)
	print(len(t1))
	print(*t1)
	print(len(t2))
	print(*t2)
	return ''
a = input()
lst = list(map(int, input().strip().split()))
print(team(lst))


import sys

def make_teams(array):
	arr_2 = sorted(range(len(array)), key=lambda k: array[k])
	teams = [[], []]
	for i in range(len(array)):
		if i % 2 == 0:
			teams[0].append(arr_2[i] + 1)
		else:
			teams[1].append(arr_2[i] + 1)
	return teams

def main():
	n = sys.stdin.readline()
	arr = [int(x) for x in sys.stdin.readline().split()]
	teams = make_teams(arr)
	for j in range(2):
		sys.stdout.write(str(len(teams[j])) + '\n')
		for i in range(len(teams[j])):
			if i == len(teams[j]) - 1:
				sys.stdout.write(str(teams[j][i]) + '\n')
			else:
				sys.stdout.write(str(teams[j][i]) + ' ')
	return
main()


n = int(input())
lst = list(map(int, input().split()))
d = {}
for (i, x) in enumerate(lst):
	if d.get(x) == None:
		d[x] = [1]
	d[x].append(i + 1)
lst.sort()
(x, y, X, Y) = (0, 0, [], [])
for (i, item) in enumerate(lst):
	if x <= y:
		X.append(d[item][d[item][0]])
		x += item
	else:
		Y.append(d[item][d[item][0]])
		y += item
	d[item][0] += 1
if n % 2 == 0:
	print(n // 2)
else:
	print(n // 2 + 1)
print(*X)
print(n // 2)
print(*Y)


n = int(input())
l = [int(i) for i in input().split()]
l = [[l[i], i] for i in range(n)]
l.sort(reverse=1)
a = 0
b = 0
one = []
two = []
for i in range(n):
	if i % 2 == 0:
		a += l[i][0]
		one.append(l[i][1] + 1)
	else:
		b += l[i][0]
		two.append(l[i][1] + 1)
print(len(one))
print(*one)
print(len(two))
print(*two)


n = int(input())
i = 0

def f(a):
	global i
	i += 1
	return (a, i)
a = sorted(list(map(f, map(int, input().split()))))
print(n // 2)
for i in a[1::2]:
	print(i[1], end=' ')
print()
print(n - n // 2)
for i in a[0::2]:
	print(i[1], end=' ')


import sys

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
n = int(input())
Arr = get_array()
myArr = []
for i in range(n):
	myArr.append((Arr[i], i + 1))
myArr.sort()
(X, Y) = ([], [])
(x_total, y_total) = (0, 0)
flag = 0
for i in range(n):
	if flag == 0:
		x_total += myArr[i][0]
		X.append(myArr[i][1])
		flag = 1
	elif flag == 1:
		y_total += myArr[i][0]
		Y.append(myArr[i][1])
		flag = 0
print(len(X))
print(*X)
print(len(Y))
print(*Y)


import time, math as mt, bisect, sys
from sys import stdin, stdout
from collections import deque
from fractions import Fraction
from collections import Counter
from collections import OrderedDict
pi = 3.141592653589793

def II():
	return int(stdin.readline())

def IO():
	return stdin.readline()

def IP():
	return map(int, stdin.readline().split())

def L():
	return list(map(int, stdin.readline().split()))

def P(x):
	return stdout.write(str(x) + '\n')

def PI(x, y):
	return stdout.write(str(x) + ' ' + str(y) + '\n')

def lcm(a, b):
	return a * b // gcd(a, b)

def gcd(a, b):
	if a == 0:
		return b
	elif b == 0:
		return a
	if a > b:
		return gcd(a % b, b)
	else:
		return gcd(a, b % a)

def readTree():
	v = int(input())
	adj = [set() for i in range(v + 1)]
	for i in range(v - 1):
		(u1, u2) = In()
		adj[u1].add(u2)
		adj[u2].add(u1)
	return (adj, v)

def bfs(adj, v):
	visited = [False] * (v + 1)
	q = deque()
	while q:
		pass

def sieve():
	li = [True] * 1000001
	(li[0], li[1]) = (False, False)
	for i in range(2, len(li), 1):
		if li[i] == True:
			for j in range(i * i, len(li), i):
				li[j] = False
	prime = []
	for i in range(1000001):
		if li[i] == True:
			prime.append(i)
	return prime

def setBit(n):
	count = 0
	while n != 0:
		n = n & n - 1
		count += 1
	return count
mx = 10 ** 7
spf = [mx] * (mx + 1)

def SPF():
	spf[1] = 1
	for i in range(2, mx + 1):
		if spf[i] == mx:
			spf[i] = i
			for j in range(i * i, mx + 1, i):
				if i < spf[j]:
					spf[j] = i
	return
mod = 10 ** 9 + 7

def solve():
	n = II()
	li = L()
	l = []
	for (i, a) in enumerate(li):
		l.append((a, i + 1))
	l.sort(reverse=True)
	(t1, t2) = ([], [])
	(c1, c2) = (0, 0)
	for i in range(n):
		if i % 2 == 0:
			t1.append(l[i][1])
			c1 += 1
		else:
			t2.append(l[i][1])
			c2 += 1
	print(c1)
	print(*t1)
	print(c2)
	print(*t2)
solve()


from math import log, ceil
from collections import defaultdict
n = int(input())
l = [int(x) for x in input().split()]
left = []
right = []
a = []
for i in range(len(l)):
	a.append([l[i], i + 1])
a.sort()
for i in range(n):
	if i % 2 == 0:
		left.append(a[i][1])
	else:
		right.append(a[i][1])
print(len(left))
print(*left)
print(len(right))
print(*right)


n = int(input())
arr = [int(x) for x in input().split()]
p = []
for (i, x) in enumerate(arr):
	p.append([x, i + 1])
p.sort()
a = []
b = []
for (i, x) in enumerate(p):
	if i % 2 == 0:
		a.append(str(x[1]))
	else:
		b.append(str(x[1]))
print(len(a))
print(' '.join(a))
print(len(b))
print(' '.join(b))


import sys
input = sys.stdin.readline
for _ in range(1):
	n = int(input())
	arr = [int(x) for x in input().split()]
	temp = [[arr[i], i] for i in range(n)]
	temp.sort()
	(a, b) = ([], [])
	for i in range((n + 1) // 2):
		if i % 2 == 0:
			if i + 1 != n - i:
				a.append(temp[i][1] + 1)
				a.append(temp[n - i - 1][1] + 1)
			else:
				a.append(temp[i][1] + 1)
		elif i + 1 == n - i:
			b.append(temp[i][1] + 1)
		else:
			b.append(temp[i][1] + 1)
			b.append(temp[n - i - 1][1] + 1)
	if abs(len(a) - len(b)) > 1:
		if len(a) > len(b):
			b.append(a.pop())
		else:
			a.append(b.pop())
	print(len(a))
	print(*a)
	print(len(b))
	print(*b)


from _collections import defaultdict
n = int(input())
al = list(map(int, input().split()))
id = defaultdict(lambda : [])
for i in range(n):
	id[al[i]] += [i + 1]
al.sort()
(s1, s2) = ([], [])
for i in range(n):
	if i % 2 == 0:
		s1 += [str(id[al[i]].pop())]
	else:
		s2 += [str(id[al[i]].pop())]
print(len(s1))
print(' '.join(s1))
print(len(s2))
print(' '.join(s2))


n = int(input())
a = list(map(int, input().split()))
m = max(a)
temp = [(a[i], i + 1) for i in range(n)]
temp.sort()
teamsum = [0, 0]
cnt = [0, 0]
teams = [[], []]
minpos = 0
i = n - 1
while cnt[0] < n // 2 and cnt[1] < n // 2:
	cnt[minpos] += 1
	teamsum[minpos] += temp[i][0]
	teams[minpos].append(temp[i][1])
	i -= 1
	if teamsum[0] > teamsum[1]:
		minpos = 1
	else:
		minpos = 0
while cnt[0] < n // 2 and i >= 0:
	if abs(teamsum[1] - teamsum[0]) <= m:
		teamsum[0] += temp[i][0]
		cnt[0] += 1
		teams[0].append(temp[i][1])
	else:
		teamsum[1] += temp[i][0]
		cnt[1] += 1
		teams[1].append(temp[i][1])
	i -= 1
while cnt[1] < n // 2 and i >= 0:
	if abs(teamsum[1] - teamsum[0]) <= m:
		teamsum[1] += temp[i][0]
		cnt[1] += 1
		teams[1].append(temp[i][1])
	else:
		teamsum[0] += temp[i][0]
		cnt[0] += 1
		teams[0].append(temp[i][1])
	i -= 1
if n % 2 == 1:
	if teamsum[0] < teamsum[1]:
		teams[0].append(temp[i][1])
	else:
		teams[1].append(temp[i][1])
print(len(teams[0]))
print(*teams[0])
print(len(teams[1]))
print(*teams[1])


n = int(input())
ar = list(map(int, input().split()))
ar1 = []
for i in range(n):
	ar1.append([ar[i], i])
ar1 = sorted(ar1)
print((n + 1) // 2)
for i in range(0, n, 2):
	print(ar1[i][1] + 1, end=' ')
print()
print(n // 2)
for i in range(1, n, 2):
	print(ar1[i][1] + 1, end=' ')


(n, t) = (int(input()), list(map(int, input().split())))
k = n // 2
(a, b) = (t[:k], t[k:])
(u, v, m) = (sum(a), sum(b), max(t))
(a, b) = (list(enumerate(a, 1)), list(enumerate(b, k + 1)))
(i, d) = (0, abs(u - v) - m)
if u > v:
	(a, b) = (b, a)
while d > 0:
	if a[i][1] < b[i][1]:
		d -= 2 * (b[i][1] - a[i][1])
		(a[i], b[i]) = (b[i], a[i])
		if d < 1:
			break
	i += 1
print(len(a))
print(' '.join((str(i) for (i, r) in a)))
print(len(b))
print(' '.join((str(i) for (i, r) in b)))


class Player:

	def __init__(self, id, skill):
		self.id = id
		self.skill = skill

	def __eq__(self, other):
		return self.id == other.id

	def __lt__(self, other):
		return self.skill < other.skill

	def __repr__(self):
		return str(self.skill)

class Team:

	def __init__(self, players, totalSkill):
		self.players = players
		self.totalSkill = totalSkill
n = int(input())
players = [Player(idx + 1, int(skill)) for (idx, skill) in enumerate(input().split())]
players = sorted(players)
teamA = Team([], 0)
teamB = Team([], 0)
for player in players:
	if teamA.totalSkill < teamB.totalSkill and len(teamA.players) - len(teamB.players) <= 1:
		teamA.players.append(player)
		teamA.totalSkill += player.skill
	else:
		teamB.players.append(player)
		teamB.totalSkill += player.skill
print(len(teamA.players))
print(' '.join([str(player.id) for player in teamA.players]))
print(len(teamB.players))
print(' '.join([str(player.id) for player in teamB.players]))


from collections import deque

def question3():
	boys = int(input())
	skills = list(map(int, input().split()))
	arr = []
	max1 = max(skills)
	for i in range(boys):
		arr.append([skills[i], i + 1])
	arr.sort(key=lambda x: x[0])
	team1 = deque([])
	team2 = deque([])
	sum1 = 0
	sum2 = 0
	for i in range(boys):
		if i < boys // 2:
			team1.append(arr[i])
			sum1 += arr[i][0]
		else:
			team2.append(arr[i])
			sum2 += arr[i][0]
	while abs(sum1 - sum2) > max1:
		k1 = team1.popleft()
		k2 = team2.pop()
		sum1 = sum1 - k1[0] + k2[0]
		sum2 = sum2 - k2[0] + k1[0]
		team2.appendleft(k1)
		team1.append(k2)
	print(len(team1))
	for i in range(len(team1)):
		print(team1[i][1], end=' ')
	print()
	print(len(team2))
	for i in range(len(team2)):
		print(team2[i][1], end=' ')
	print()
remained_test_cases = 1
while remained_test_cases > 0:
	question3()
	remained_test_cases -= 1


n = int(input())
a = [int(i) for i in input().split()]
dic = {}
for i in range(n):
	dic[a[i]] = []
for i in range(n):
	dic[a[i]].append(i + 1)
a.sort()
f = []
s = []
for i in range(n):
	if i & 1:
		f.append(dic[a[i]][-1])
	else:
		s.append(dic[a[i]][-1])
	dic[a[i]].pop()
print(len(f))
print(*f)
print(len(s))
print(*s)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from bisect import bisect_left
from collections import Counter
n = int(input())
arr = sorted([(x, i) for (i, x) in enumerate(map(int, input().split()))])[::-1]
a = []
b = []
f = 0
m = 0
sum_a = 0
sum_b = 0
for i in range(n):
	m = max(m, arr[i][0])
	if f == 0:
		a.append(arr[i][1] + 1)
		sum_a += arr[i][0]
		f = 1
	else:
		b.append(arr[i][1] + 1)
		sum_b += arr[i][0]
		f = 0
if abs(sum_a - sum_b) > m:
	if sum(a) > sum(b):
		var = a[1]
		a.remove(var)
		b.append(var)
	else:
		var = b[1]
		b.remove(var)
		a.append(var)
print(len(a))
print(*a)
print(len(b))
print(*b)


import sys
import math as mt
import bisect
t = 1
for __ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ind = {}
	curind = {}
	for i in range(n):
		if ind.get(l[i], -1) == -1:
			ind[l[i]] = []
		ind[l[i]].append(i)
		curind[l[i]] = 0
	l.sort(reverse=True)
	if n % 2 == 0:
		x = n // 2
		y = n // 2
	else:
		x = n // 2 + 1
		y = n // 2
	i = 0
	print(x)
	while i < n:
		print(ind[l[i]][curind[l[i]]] + 1, end=' ')
		curind[l[i]] += 1
		i += 2
	i = 1
	print()
	print(y)
	while i < n:
		print(ind[l[i]][curind[l[i]]] + 1, end=' ')
		curind[l[i]] += 1
		i += 2
	print()


import sys
import heapq
import math
sys.setrecursionlimit(100000)
from collections import deque
from collections import defaultdict
from collections import Counter

def PRINT(lst, sep=' '):
	print(sep.join(map(str, lst)))
I = lambda : list(map(int, input().split(' ')))

def solve(lst):
	n = len(lst)
	nn = n // 2
	ll = [(ele, i + 1) for (i, ele) in enumerate(lst)]
	ll.sort()
	x = []
	y = []
	sy = 0
	sx = 0
	while max(len(x), len(y)) < (nn if n % 2 == 0 else nn + 1) and len(ll) > 0:
		(val, name) = ll.pop()
		sx += val
		x.append(name)
		while max(len(x), len(y)) < (nn if n % 2 == 0 else nn + 1) and len(ll) > 0 and (sx > sy):
			(val, name) = ll.pop()
			sy += val
			y.append(name)

	def fill(arr):
		while ll:
			(s, _) = ll.pop()
			arr.append(_)
	if n % 2 == 0:
		if len(x) == nn:
			fill(y)
		if len(y) == nn:
			fill(x)
	elif n % 2 == 1:
		if len(x) == nn + 1:
			fill(y)
		if len(y) == nn + 1:
			fill(x)
	print(len(x))
	PRINT(x)
	print(len(y))
	PRINT(y)
	return
n = int(input())
lst = I()
solve(lst)


n = int(input())
arr = sorted([(int(x), i) for (i, x) in enumerate(input().split())])
print((len(arr) + 1) // 2)
for i in arr[::2]:
	print(i[1] + 1, end=' ')
print()
print(len(arr) // 2)
for i in arr[1::2]:
	print(i[1] + 1, end=' ')


b = []
f = []
s = []
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
	b.append((a[i], i + 1))
c = 0
for i in sorted(b):
	if not c % 2:
		f.append(i)
	else:
		s.append(i)
	c += 1
print(len(f))
for i in f:
	if i != f[len(f) - 1]:
		print(i[1], end=' ')
	else:
		print(i[1])
print(len(s))
for i in s:
	print(i[1], end=' ')


n = int(input())
a = list(map(int, input().split()))
di = {}
for i in range(len(a)):
	di[i] = di.get(i, 0) + a[i]
d = sorted(di.items(), key=lambda kv: (kv[1], kv[0]))
dic = dict(d)
list1 = list()
list2 = list()
i = 0
for keys in dic:
	if i % 2:
		list2.append(keys + 1)
	else:
		list1.append(keys + 1)
	i += 1
len1 = int((n + 1) / 2)
len2 = n - len1
print(len1)
for i in range(len1):
	print(list1[i], end=' ')
print('\n{}'.format(len2))
for i in range(len2):
	print(list2[i], end=' ')


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
n = Int()
a = array()
a = [(a[i], i) for i in range(n)]
a.sort()
t1 = []
t2 = []
for i in range(n):
	if i % 2 == 0:
		t1.append(a[i][1] + 1)
	else:
		t2.append(a[i][1] + 1)
print(len(t1))
print(*t1)
print(len(t2))
print(*t2)


n = int(input())
p = list(map(int, input().split()))
l = []
for i in range(n):
	l.append([p[i], i + 1])
l.sort()
f = [l[0][1]]
s = [l[1][1]]
s1 = l[0][0]
s2 = l[1][0]
for i in range(2, n):
	if s1 > s2:
		s.append(l[i][1])
		s2 = s2 + l[i][0]
	elif s2 > s1:
		f.append(l[i][1])
		s1 = s1 + l[i][0]
	elif s2 == s1:
		if len(f) > len(s):
			s.append(l[i][1])
			s2 = s2 + l[i][0]
		else:
			f.append(l[i][1])
			s1 = s1 + l[i][0]
print(len(f))
for i in range(len(f)):
	if i != len(f) - 1:
		print(f[i], end=' ')
	else:
		print(f[i])
print(len(s))
for i in range(len(s)):
	if i != len(s) - 1:
		print(s[i], end=' ')
	else:
		print(s[i])


n = int(input())
l = [int(i) for i in input().split()]
t = sorted(l)
x = 0
y = 0
d = dict()
for i in range(len(l)):
	if l[i] in d:
		d[l[i]].append(i + 1)
	else:
		d[l[i]] = [i + 1]
a = []
b = []
for i in range(len(t)):
	if x < y:
		a.append(t[i])
		x += t[i]
	else:
		b.append(t[i])
		y += t[i]
print(len(a))
for i in a:
	print(d[i][0], end=' ')
	d[i].pop(0)
print()
print(len(b))
for i in b:
	print(d[i][0], end=' ')
	d[i].pop(0)


n = int(input())
guys = list(map(int, input().split()))
guys = list(enumerate(guys))
guys.sort(key=lambda x: x[1], reverse=True)
team1 = []
skill1 = 0
team2 = []
skill2 = 0
for (number, skill) in guys:
	if skill1 > skill2:
		if len(team2) - len(team1) >= 1:
			team1.append(number + 1)
			skill1 += skill
			continue
		team2.append(number + 1)
		skill2 += skill
	else:
		if len(team1) - len(team2) >= 1:
			team2.append(number + 1)
			skill2 += skill
			continue
		team1.append(number + 1)
		skill1 += skill
print(len(team1))
for i in team1:
	print(i, end=' ')
print()
print(len(team2))
for i in team2:
	print(i, end=' ')
print()


import sys
import math as mt
import bisect
input = sys.stdin.buffer.readline
t = 1
for __ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ans = []
	for i in range(n):
		ans.append([l[i], i + 1])
	ans.sort(reverse=True)
	if n % 2 == 0:
		x = n // 2
		y = n // 2
	else:
		x = n // 2 + 1
		y = n // 2
	i = 0
	print(x)
	while i < n:
		print(ans[i][1], end=' ')
		i += 2
	i = 1
	print()
	print(y)
	while i < n:
		print(ans[i][1], end=' ')
		i += 2
	print()


n = int(input())
arr = list(map(int, input().split()))
arr = [(v, i + 1) for (i, v) in enumerate(arr)]
arr.sort()
left = arr[:n // 2]
right = arr[n // 2:]
left_sum = sum([v for (v, i) in left])
right_sum = sum([v for (v, i) in right])
max_player = max([v for (v, i) in arr])
for i in range(n // 2):
	if abs(right_sum - left_sum) <= max_player:
		for j in range(i + 1, n // 2):
			if abs(right_sum - left_sum) <= max_player:
				break
			weight = right[j][0] - left[i][0]
			(left[i], right[j]) = (right[j], left[i])
			left_sum += weight
			right_sum -= weight
		break
	weight = right[i][0] - left[i][0]
	(left[i], right[i]) = (right[i], left[i])
	left_sum += weight
	right_sum -= weight
print(len(left))
print(*[i for (v, i) in left])
print(len(right))
print(*[i for (v, i) in right])


a = int(input())
b = input().split()
b = sorted([[int(b[i]), str(i + 1)] for i in range(0, a)], reverse=True)
(c, d) = ([], [])
(sc, sd) = (0, 0)
while len(b) > 1:
	if sc > sd:
		d.append(b.pop()[1])
		c.append(b.pop()[1])
	else:
		c.append(b.pop()[1])
		d.append(b.pop()[1])
if len(b):
	if sc > sd:
		d.append(b.pop()[1])
	else:
		c.append(b.pop()[1])
print(len(c))
print(' '.join(c))
print(len(d))
print(' '.join(d))


n = int(input())
a = list(map(int, input().split()))
arr = []
for i in range(n):
	arr.append((a[i], i + 1))
arr.sort(reverse=True)
t1 = []
t2 = []
sum1 = 0
sum2 = 0
ex = -1
if n % 2 == 1:
	ex = arr[n - 1][1]
	n -= 1
for i in range(0, n, 2):
	if arr[i][0] >= arr[i + 1][0]:
		mx = arr[i][0]
		mn = arr[i + 1][0]
		imx = arr[i][1]
		imn = arr[i + 1][1]
	else:
		mn = arr[i][0]
		mx = arr[i + 1][0]
		imn = arr[i][1]
		imx = arr[i + 1][1]
	if sum1 <= sum2:
		sum1 += mx
		sum2 += mn
		t1.append(imx)
		t2.append(imn)
	else:
		sum1 += mn
		sum2 += mx
		t1.append(imn)
		t2.append(imx)
if sum1 < sum2 and ex != -1:
	t1.append(ex)
elif sum2 <= sum1 and ex != -1:
	t2.append(ex)
print(len(t1))
for i in range(len(t1)):
	print(t1[i], end=' ')
print()
print(len(t2))
for i in range(len(t2)):
	print(t2[i], end=' ')


import sys, os.path
from collections import *
from copy import *
import math
mod = 10 ** 9 + 7
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
n = int(input())
a = list(map(int, input().split()))
pair = []
for i in range(n):
	b = [a[i], i + 1]
	pair.append(b)
pair.sort()
team1 = []
team2 = []
for i in range(n):
	if i % 2 == 0:
		team1.append(pair[i])
	else:
		team2.append(pair[i])
print(len(team1))
for i in range(len(team1)):
	print(team1[i][1], end=' ')
print()
print(len(team2))
for i in range(len(team2)):
	print(team2[i][1], end=' ')


import sys
input = sys.stdin.buffer.readline
I = lambda : list(map(int, input().split()))
(n,) = I()
l = I()
ll = []
f = {}
for i in range(n):
	ll.append([l[i], i])
	f[i] = l[i]
ll.sort(reverse=True)
x = []
y = []
xs = 0
ys = 0
xm = max(l)
for i in range(n):
	if i % 2 == 0:
		x.append(ll[i][1])
		xs += ll[i][0]
	else:
		y.append(ll[i][1])
		ys += ll[i][0]
while abs(xs - ys) > xm:
	temp = x.pop()
	xs -= f[temp]
	y.append(temp)
	ys += f[temp]
print(len(x))
for i in x:
	print(i + 1, end=' ')
print()
print(len(y))
for i in y:
	print(i + 1, end=' ')


from _collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
pos = defaultdict(lambda : [])
for i in range(n):
	pos[a[i]] += [i + 1]
a.sort()
sum1 = []
sum2 = []
for i in range(n):
	if i % 2 == 0:
		sum1 += [str(pos[a[i]].pop())]
	else:
		sum2 += [str(pos[a[i]].pop())]
print(len(sum1))
print(' '.join(sum1))
print(len(sum2))
print(' '.join(sum2))


n = int(input())
arr = list(map(int, input().split()))
x = []
y = []
sx = 0
sy = 0
i = 0
ml = []
z = 0
while z < n:
	ml.append([arr[z], z + 1])
	z += 1
ml.sort()
for k in ml:
	if sx <= sy:
		sx += k[0]
		x.append(k[1])
	else:
		sy += k[0]
		y.append(k[1])
	i += 1
print(len(x))
print(*x)
print(len(y))
print(*y)


a = int(input())
z = list(map(int, input().split()))
ans = []
for i in range(len(z)):
	ans.append([z[i], i])
ans.sort()
flag = 0
tan = []
i = 0
one = []
two = []
while i < len(ans):
	if flag == 0:
		one.append(ans[i][1] + 1)
		i += 1
		if i < len(ans):
			two.append(ans[i][1] + 1)
		flag = 1
		i += 1
	else:
		one.append(ans[i][1] + 1)
		i += 1
		if i < len(ans):
			two.append(ans[i][1] + 1)
		flag = 1
		i += 1
print(len(one))
print(*one)
print(len(two))
print(*two)


n = int(input())
a = map(int, input().split())
a = sorted(enumerate(a, 1), key=lambda x: x[1])
a = list(a)
(t1, t2) = ([], [])
first = True
while len(a):
	if first:
		t1.append(a.pop()[0])
	else:
		t2.append(a.pop()[0])
	first = not first
print(len(t1))
print(*t1)
print(len(t2))
print(*t2)