In the Bus of Characters there are $n$ rows of seat, each having $2$ seats. The width of both seats in the $i$-th row is $w_i$ centimeters. All integers $w_i$ are distinct.

Initially the bus is empty. On each of $2n$ stops one passenger enters the bus. There are two types of passengers:   an introvert always chooses a row where both seats are empty. Among these rows he chooses the one with the smallest seats width and takes one of the seats in it;  an extrovert always chooses a row where exactly one seat is occupied (by an introvert). Among these rows he chooses the one with the largest seats width and takes the vacant place in it. 

You are given the seats width in each row and the order the passengers enter the bus. Determine which row each passenger will take.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 200\,000$) — the number of rows in the bus.

The second line contains the sequence of integers $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 10^{9}$), where $w_i$ is the width of each of the seats in the $i$-th row. It is guaranteed that all $w_i$ are distinct.

The third line contains a string of length $2n$, consisting of digits '0' and '1' — the description of the order the passengers enter the bus. If the $j$-th character is '0', then the passenger that enters the bus on the $j$-th stop is an introvert. If the $j$-th character is '1', the the passenger that enters the bus on the $j$-th stop is an extrovert. It is guaranteed that the number of extroverts equals the number of introverts (i. e. both numbers equal $n$), and for each extrovert there always is a suitable row.


-----Output-----

Print $2n$ integers — the rows the passengers will take. The order of passengers should be the same as in input.


-----Examples-----
Input
2
3 1
0011

Output
2 1 1 2 

Input
6
10 8 9 11 13 5
010010011101

Output
6 6 2 3 3 1 4 4 1 2 5 5 



-----Note-----

In the first example the first passenger (introvert) chooses the row $2$, because it has the seats with smallest width. The second passenger (introvert) chooses the row $1$, because it is the only empty row now. The third passenger (extrovert) chooses the row $1$, because it has exactly one occupied seat and the seat width is the largest among such rows. The fourth passenger (extrovert) chooses the row $2$, because it is the only row with an empty place.

Difficulty: interview

Starter code:

Solutions:
from collections import deque
def main():
    n = int(input())
    a = list(map(int, input().split()))
    s = input()
    b = []
    for i in range(n):
        b.append([a[i], i + 1])
    b.sort()
    ans = []
    count1, count2 = 0, 0
    c = deque([])
    for i in range(2 * n):
        if (s[i] == '0'):
            ans.append(b[count1][1])
            c.append(b[count1][1])
            count1 += 1
        else:
            ans.append(c[-1])
            c.pop()
            count2 += 1
    for i in range(2 * n):
        print(ans[i], end=' ')
main()

n = int(input())
w = [int(k) for k in input().split()]
for i in range(n):
    w[i] = [i + 1, w[i], 0]
w.sort(key=lambda e: e[1])
nextIntro = 0
result = [0 for _ in range(2 * n)]
unfilled = []
for index, v in enumerate(input()[:2*n]):
    if v == '0':
        result[index] = w[nextIntro][0]
        unfilled.append(nextIntro)
        nextIntro += 1
    elif v == '1':
        result[index] = w[unfilled.pop()][0]
print(*result)
        


input()
intro = sorted([(-x,i+1) for i,x in enumerate(map(int, input().split()))])
extro = []
line = input()
sol = []
for c in line:
    if c == '0':
        w, r = intro.pop()
        extro.append((w, r))
        sol.append(str(r))
    else:
        w, r = extro.pop()
        sol.append(str(r))
print(' '.join(sol))

import math;
import time;
import bisect;
def getIntList():
    return list(map(int, input().split()));
def getTransIntList(n):
    first=getIntList();
    m=len(first);
    result=[[0]*n for _ in range(m)];
    for i in range(m):
        result[i][0]=first[i];
    for j in range(1, n):
        curr=getIntList();
        for i in range(m):
            result[i][j]=curr[i];
    return result;
n=int(input());
w=getIntList();
s=input();
p=[int(s[i]) for i in range(2*n)];
seatInt=[(w[i], i) for i in range(n)];
seatInt.sort();
currI=0;
seatExt=[];
result=[0]*(2*n);
for i in range(2*n):
    if p[i]==0:
        result[i]=seatInt[currI][1]+1
        bisect.insort(seatExt, seatInt[currI]);
        currI+=1;
    else:
        result[i]=seatExt.pop()[1]+1;
print(' '.join(map(str,result)))

n=int(input())


w=list(map(int,input().split()))


s=input()

for i in range(n):
    w[i]=[w[i],i]
w.sort(reverse=True)
exos=[]
locs=[-1 for i in range(2*n)]
for i in range(2*n):
    if(s[i]=='0'):
        exos.append(w.pop())
        locs[i]=exos[-1][1]+1
    else:
        temp=exos.pop()
        locs[i]=temp[1]+1
print(*locs)



#!/usr/bin/env python3

from collections import deque

n = int(input().strip())
wis = list(map(int, input().strip().split()))
cs = input().strip()

pl = list(range(1, n + 1))
pl.sort(key=lambda p: wis[p - 1])

i = 0
stack = deque()
res = []
for c in cs:
	if c == '0':
		stack.append(pl[i])
		res.append(pl[i])
		i += 1
	else:
		res.append(stack.pop())

print(' '.join(map(str, res)))


n = int(input())
W = [int(x) for x in input().split()]
W = sorted((w,i) for i,w in enumerate(W))

P = input()

smallfree = 0
smallhalf = 0
highfree = n-1
highasdk = n-1

R = []

from collections import defaultdict as dd, deque

Q = deque()

for p in P:
    if p == '0':
        R.append(W[smallfree][1])
        Q.append(smallfree)
        smallfree += 1
    else:
        seat = Q.pop()
        R.append(W[seat][1])
print(*[r+1 for r in R])




from heapq import heappop,heappush
n=int(input())
c=1
w={}
wh=[]
for i in input().split():
    i=int(i)
    w[i]=c
    c+=1
    heappush(wh,i)
o=''
ss=[]
for i in input():
    if i=='0':
        ss+=[str(w[heappop(wh)])]
        o+=ss[-1]+' '
    else:
        o+=ss[-1]+' '
        ss.pop(-1)
print(o)



n = int(input())

widths = [(int(x), c) for c, x in enumerate(input().split())]

widths.sort()

passengers = input()

seating = ""
stack = []
i = 0

for pi in passengers:
	if pi == '1':
		seating += str(stack[-1][1]+1) + " "
		stack.pop()
	else:
		stack.append(widths[i])		
		seating += str(stack[-1][1]+1) + " "				
		i += 1

print(seating[:-1])


def main():
    n = int(input())
    j = list(map(int, input().split()))
    for i in range(n):
        j[i] = [j[i], i + 1]
    j.sort()
    j = j[::-1]
    e = []
    s = input()
    for i in range(2 * n):
        if s[i] == '0':
            print(j[-1][1], end=' ')
            e.append(j[-1])
            j.pop()
        else:
            print(e[-1][1], end=' ')
            e.pop()
main()

# your code goes here
N = int(input())

w = list(map(int,input().split(' ')))
key = [i+1 for i in range(N)]

w_dict = dict(zip(key,w))

w_dict = sorted(w_dict.items(), key=lambda x: x[1])

number = [row[0] for row in w_dict]

passenger = input()
ans = []
gaikouteki = []
now = 0
for i in passenger:
	if i == '0':
		ans.append(number[now])
		gaikouteki.append(number[now])
		now += 1
	else:
		ans.append(gaikouteki[-1])
		gaikouteki.pop()
print(' '.join(map(str,ans)))

n = int(input())
w=list(map(int, input().split()))
a=sorted(list(range(1,n+1)),key=lambda i:w[i-1])
i,s,o=0,[],[]
for c in input():
    if c=='0':
        o.append(a[i])
        s.append(a[i])
        i+=1
    else:
        o.append(s.pop())
print(*o)


from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
z = defaultdict(list)
temp1 = []
temp2 = []
for i in range(n):
    z[a[i]] = i+1
    temp1.append(a[i])
s = input()
temp1.sort(reverse=True)

for i in s:
    if(i=='0'):
        x = temp1.pop()
        print(z[x],end=' ')
        temp2.append(x)
    else:
        print(z[temp2.pop()],end=' ')

n=int(input())
w=list(map(int, input().split()))
w =sorted(range(len(w)), key=w.__getitem__)
w = iter(w)

e = list(input())
from collections import deque
s = deque()
for e1 in e:
    if e1 == '0':
        x = next(w)+1
        print(x, end = ' ')
        s.append(x)
    else:
        print(s.pop(), end = ' ')

n=int(input())
s=list(map(int,input().split()))
strr=input()
dic={}
for i in range(0,n):
    dic[s[i]]=i+1 
list0=s[::]
list1=[]
list2=[]
m=""
k=0
j=0
list0.sort()
for i in strr:
    if i=='0':
        m+=str(dic[list0[j]])+" "
        list1+=[list0[j]]
        k=k+1
        j=j+1
        #del(list0[0])
    else:
        m+=str(dic[list1[k-1]])+" "
        del(list1[k-1])
        k=k-1
print(m)

"""Problem B - Bus of Characters.

http://codeforces.com/contest/982/problem/B

In the Bus of Characters there are `n` rows of seat, each having `2` seats.
The width of both seats in the `i`-th row is `w_i` centimeters. All integers
`w_i` are distinct.

Initially the bus is empty. On each of `2n` stops one passenger enters the
bus. There are two types of passengers:

- an introvert always chooses a row where both seats are empty. Among these
rows he chooses the one with the smallest seats width and takes one of the
seats in it;

- an extrovert always chooses a row where exactly one seat is occupied (by an
introvert). Among these rows he chooses the one with the largest seats width
and takes the vacant place in it.

You are given the seats width in each row and the order the passengers enter
the bus. Determine which row each passenger will take.

Input:

The first line contains a single integer `n` (`1 <= n <= 200\,000`) — the
number of rows in the bus.

The second line contains the sequence of integers `w_1, w_2, ..., w_n` (`1 <=
w_i <= 10^{9}`), where `w_i` is the width of each of the seats in the `i`-th
row. It is guaranteed that all `w_i` are distinct.

The third line contains a string of length `2n`, consisting of digits '0' and
'1' — the description of the order the passengers enter the bus. If the `j`-th
character is '0', then the passenger that enters the bus on the `j`-th stop is
an introvert. If the `j`-th character is '1', the the passenger that enters the
bus on the `j`-th stop is an extrovert. It is guaranteed that the number of
extroverts equals the number of introverts (i. e. both numbers equal `n`), and
for each extrovert there always is a suitable row.

Output:

Print `2n` integers — the rows the passengers will take. The order of
passengers should be the same as in input.

"""
import logging
import collections


fmt = '%(levelname)s - %(name)s (line:%(lineno)s) - %(message)s'
formatter = logging.Formatter(fmt)

ch = logging.StreamHandler()
ch.setLevel(logging.NOTSET)
ch.setFormatter(formatter)

logger = logging.getLogger('bus_of_characters')
logger.setLevel(logging.NOTSET)
logger.addHandler(ch)


def solve(w, s):
    free = collections.deque()
    used = collections.deque()

    for w in sorted(enumerate(w), key=lambda x: x[1]):
        free.append([w[0] + 1, w[1]])
    
    ids = [-1] * len(s)

    order = []
    for pid, p in enumerate(s):
        logger.debug('pid: %s', pid)
        if p == '0':
            taken = free.popleft(), 
            used.appendleft(taken)
            # order.append(pid, taken[0])
        else:
            logger.debug('used %s', used)
            taken = used.popleft()
        #order.append([pid, taken[0]])
        ids[pid] = taken[0]

    return [x for x, y in ids]



def main():
    n = int(input().strip())
    w = [int(x) for x in input().strip().split()]
    s = input().strip()

    result = solve(w, s)
    print(' '.join(map(str, result)))


def __starting_point():
    main()

__starting_point()

n = int(input().strip())
temp = input().strip().split()
w = []
for j in range(len(temp)):
	w.append([int(temp[j]),j])

w.sort()
#print(w)
passenger = input().strip()

biggest_intro = []
smallest_index = 0

for i in range(2*n):
	if passenger[i] == '0':
		#introvert
		#smallest_empty = w[smallest_index][1]		#actual index
		print(w[smallest_index][1]+1, end=' ')
		biggest_intro.append(smallest_index)		#non-actual index, bigger width at the end
		smallest_index+=1
	elif passenger[i] == '1':
		b = biggest_intro.pop()
		print(w[b][1]+1,end=' ')

	#print(biggest_intro)
print()


n = int(input())
cl = list(map(int, input().split()))
s = input()
dic = {}
for x in range(n):
  dic.update({cl[x]:x+1})

cl = sorted(cl)
pl = []
res = ''
pos1=0
for c in s:
  if c=='0':
    pl.append(cl[pos1])
    res+=str(dic[cl[pos1]])+' '
    pos1+=1
  if c=='1':
    mx = pl[-1]
    res+=str(dic[mx])+ ' '
    pl.pop(-1)

print(res)

n = int(input())
l = 2 * n
w = [int(i) for i in input().split()]
pas = input()
seat = [i for i in w]
seat.sort()
d = {}
for i in range(len(w)):
	d[w[i]] = i
i = 0
w1 = [0] * l
j = 0
wkend = " "
for k in range(l):
	if k == l - 1:
		wkend = "\n"
	if pas[k] == "0":
		wkindex = d[seat[i]] + 1
		print(wkindex, end = wkend)
		j += 1
		w1[j] = wkindex
		i += 1
	else:
		print(w1[j], end = wkend)
		j -= 1


# Python program for implementation of MergeSort
 
# Merges two subarrays of arr[].
# First subarray is arr[l..m]
# Second subarray is arr[m+1..r]
def merge(arr,temp, l, m, r):
    n1 = m - l + 1
    n2 = r- m
 
    # create temp arrays
    L1 = [0] *n1
    L2= [0] *n1
    R1 = [0] *n2
    R2 = [0] *n2
    # Copy data to temp arrays L[] and R[]
    for i in range(0 , n1):
        L1[i] = arr[l + i]
        L2[i] = temp[l + i]
    for j in range(0 , n2):
        R1[j] = arr[m + 1 + j]
        R2[j] = temp[m + 1 + j]
 
    # Merge the temp arrays back into arr[l..r]
    i = 0     # Initial index of first subarray
    j = 0     # Initial index of second subarray
    k = l     # Initial index of merged subarray
 
    while i < n1 and j < n2 :
        if L1[i] <= R1[j]:
            arr[k] = L1[i]
            temp[k]= L2[i]
            i += 1
        else:
            arr[k] = R1[j]
            temp[k]= R2[j]
            j += 1
        k += 1
 
    # Copy the remaining elements of L[], if there
    # are any
    while i < n1:
        arr[k] = L1[i]
        temp[k] = L2[i]
        i += 1
        k += 1
 
    # Copy the remaining elements of R[], if there
    # are any
    while j < n2:
        arr[k] = R1[j]
        temp[k] = R2[j]
        j += 1
        k += 1
 
# l is for left index and r is right index of the
# sub-array of arr to be sorted
def mergeSort(arr,temp,l,r):
    if l < r:
 
        # Same as (l+r)/2, but avoids overflow for
        # large l and h
        m = (l+(r-1))//2
 
        # Sort first and second halves
        mergeSort(arr,temp, l, m)
        mergeSort(arr,temp, m+1, r)
        merge(arr,temp, l, m, r)
# Driver code to test above
n=int(input())
arr=list(map(int,input().split()))
temp=[]
for i in range(n):
    temp.append(i+1)
j=0
k=-1
arrx=[0]*n
mergeSort(arr,temp,0,n-1)
    #print(temp[i],temp1[temp[i]])
#print(temp1)
s=str(input())
arry=[0]*len(s)
arrn=[0]
for i in range(len(s)):
    if(s[i]=='0'):
        arry[i]=temp[j]
        arrx[temp[j]-1]+=1
        arrn.append(temp[j])
        j+=1
        
    if(s[i]=='1'):
        arry[i]=arrn[-1]
        del arrn[-1]
    #print(j,k)
print(' '.join(map(str, arry))) 


# n = int(input())
# arr = list(map(int,input().split()))
# k,d = map(int,input().split())
# n = int(input())
import sys
import math

def fun():
    n = int(input())
    arr = list(map(int, input().split()))
    enter_list = input()

    width_list = [[i+1,arr[i]] for i in range(n)]
    width_list.sort(key=lambda x:x[-1])

    j = 0
    seated_list = [width_list[0]]
    all_list = [width_list[0][0]]
    # print(width_list[j][0], end='')
    j += 1
    for c in enter_list[1:]:
        if c == '0':
            seated_list.append(width_list[j])
            # print("", width_list[j][0], end='')
            all_list.append(width_list[j][0])
            j += 1
        else:
            # print("", seated_list[-1][0], end='')
            all_list.append(seated_list[-1][0])
            seated_list.pop()
    all_list = [str(i) for i in all_list]
    print(' '.join(all_list))

def __starting_point():
    fun()

# print(str)

__starting_point()

n = int(input())
a = [int(i) for i in input().split()]
s = input()

mp = {}
for i in range(n):
    mp[a[i]] = i+1
a.sort()

intr=0
extr=0
first=mp[a[0]]
st = []
ans = []
for i in range(len(s)):
    if s[i] == '0':
        ans += [mp[a[intr]]]
        st.append(mp[a[intr]])
        intr+=1
    else:
        ans+=[st.pop()]
print(*ans)
        
            
            
    


#!/usr/bin/env python3
# -*- encoding: utf-8 -*-

import sys

def main():
    n = int(sys.stdin.readline())
    w = sys.stdin.readline().split()
    w = [(int(w[i]),i) for i in range(n)]
    p = [i for i in sys.stdin.readline().strip()]
    w.sort()
    res = []
    intro, extro = 0, []
    for pa in p:
        if pa == '0':
            extro.append(w[intro][1])
            res.append(str(w[intro][1]+1))
            intro +=1
        else:
            s = extro.pop()
            res.append(str(s+1))
    print(' '.join(res))
main()


n = int(input())

w = list(map(int, input().split()))
for i, ww in enumerate(w):
    w[i] = (ww, i + 1)
p = input()

w = sorted(w)
import heapq
que = []

t = 0
ans = []

for s in p:
    if s == '0':
        heapq.heappush(que,w[t])
        ans.append(w[t][1])
        t += 1
    else:
        head = que.pop()

        # print(head)
        ans.append(head[1])

print(*ans)

n = int(input())
line = input().split()
w = []
for i in range(n):
    w.append((int(line[i]), i+1))
w = sorted(tuple(w))
cur = 0
st = []
res = []
for ch in input():
    if ch == '0':
        st.append(w[cur][1])
        res.append(w[cur][1])
        cur += 1
    else:
        res.append(st[-1])
        st.pop()
print(' '.join(str(item) for item in res))