The next "Data Structures and Algorithms" lesson will be about Longest Increasing Subsequence (LIS for short) of a sequence. For better understanding, Nam decided to learn it a few days before the lesson.

Nam created a sequence a consisting of n (1 ≤ n ≤ 10^5) elements a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5). A subsequence a_{i}_1, a_{i}_2, ..., a_{i}_{k} where 1 ≤ i_1 < i_2 < ... < i_{k} ≤ n is called increasing if a_{i}_1 < a_{i}_2 < a_{i}_3 < ... < a_{i}_{k}. An increasing subsequence is called longest if it has maximum length among all increasing subsequences. 

Nam realizes that a sequence may have several longest increasing subsequences. Hence, he divides all indexes i (1 ≤ i ≤ n), into three groups: group of all i such that a_{i} belongs to no longest increasing subsequences. group of all i such that a_{i} belongs to at least one but not every longest increasing subsequence. group of all i such that a_{i} belongs to every longest increasing subsequence. 

Since the number of longest increasing subsequences of a may be very large, categorizing process is very difficult. Your task is to help him finish this job.


-----Input-----

The first line contains the single integer n (1 ≤ n ≤ 10^5) denoting the number of elements of sequence a.

The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5).


-----Output-----

Print a string consisting of n characters. i-th character should be '1', '2' or '3' depending on which group among listed above index i belongs to.


-----Examples-----
Input
1
4

Output
3

Input
4
1 3 2 5

Output
3223

Input
4
1 5 2 3

Output
3133



-----Note-----

In the second sample, sequence a consists of 4 elements: {a_1, a_2, a_3, a_4} = {1, 3, 2, 5}. Sequence a has exactly 2 longest increasing subsequences of length 3, they are {a_1, a_2, a_4} = {1, 3, 5} and {a_1, a_3, a_4} = {1, 2, 5}.

In the third sample, sequence a consists of 4 elements: {a_1, a_2, a_3, a_4} = {1, 5, 2, 3}. Sequence a have exactly 1 longest increasing subsequence of length 3, that is {a_1, a_3, a_4} = {1, 2, 3}.

Difficulty: HARD
Tags: String algorithms

Greedy algorithms

Dynamic programming

Mathematics

Data structures
Skill types: Dynamic programming

Data structures

Greedy algorithms

Starter code:

Solutions:
def main():

	def parser():
		while 1:
			data = list(input().split(' '))
			for number in data:
				if len(number) > 0:
					yield number
	input_parser = parser()
	gets = lambda : next(input_parser)

	def getNum():
		data = gets()
		try:
			return int(data)
		except ValueError:
			return float(data)
	from bisect import bisect_left
	MAXA = int(9000000000.0)
	n = getNum()
	RANGN = range(n)
	a = [getNum() for _ in RANGN]
	revlis = []
	g = [MAXA] * n
	for i in reversed(RANGN):
		x = -a[i]
		pt = bisect_left(g, x)
		revlis.append(pt + 1)
		if x < g[pt]:
			g[pt] = x
	hlis = max(revlis)
	(lis, inlis) = ([], [])
	d = [0] * n
	for i in RANGN:
		g[i] = MAXA
	for i in RANGN:
		pt = bisect_left(g, a[i])
		lis.append(pt + 1)
		inlis.append(lis[i] + revlis[n - i - 1] > hlis)
		d[pt] += inlis[-1]
		if a[i] < g[pt]:
			g[pt] = a[i]
	print(''.join(['32'[d[lis[i] - 1] > 1] if inlis[i] else '1' for i in RANGN]))
main()


n = int(input())
secuencia = [None] * n
ma = 0
for (num, e) in enumerate(input().strip().split()):
	en = int(e)
	secuencia[num] = [en, 0, num]
	ma = max(ma, en)
escritura = ['1'] * len(secuencia)
bit = [0] * (ma + 1)

def max_x(x, l):
	suma = 0
	while x != 0:
		suma = max(suma, l[x])
		x -= x & -x
	return suma

def update_x(x, l, max_n, val):
	while x <= max_n:
		if val > l[x]:
			l[x] = val
		else:
			return
		x += x & -x

def new_get_secuence(e):
	num = secuencia[e][0]
	maximo = max_x(num - 1, bit) + 1
	update_x(num, bit, ma, maximo)
	return maximo
for e in range(n):
	secuencia[e][1] = new_get_secuence(e)
secuencia.sort(key=lambda x: (-x[1], -x[2]))
ultimos = [(ma + 1, 0, n)]
partir = 0
moment_max = secuencia[0][1]
usados = []
for e in secuencia:
	if e[1] < moment_max:
		if len(usados) == 1:
			escritura[usados[0][2]] = '3'
		else:
			for y in usados:
				escritura[y[2]] = '2'
		ultimos = usados
		usados = []
		moment_max -= 1
	for element in ultimos:
		if e[2] < element[2]:
			if e[0] < element[0]:
				usados.append(e)
				break
		else:
			break
if len(usados) == 1:
	escritura[usados[0][2]] = '3'
else:
	for y in usados:
		escritura[y[2]] = '2'
print(''.join(escritura))


N = int(input())
A = list(map(int, input().split()))
maxa = max(A)

def upd(ftree, x, v):
	while x <= maxa:
		ftree[x] = max(ftree[x], v)
		x += x & -x

def qry(ftree, x):
	res = 0
	while x:
		res = max(res, ftree[x])
		x -= x & -x
	return res
st_len = [0 for i in range(N)]
ftree = [0 for i in range(maxa + 1)]
for i in range(N - 1, -1, -1):
	st_len[i] = qry(ftree, maxa + 1 - A[i] - 1) + 1
	upd(ftree, maxa + 1 - A[i], st_len[i])
ed_len = [0 for i in range(N)]
ftree = [0 for i in range(maxa + 1)]
for i in range(N):
	ed_len[i] = qry(ftree, A[i] - 1) + 1
	upd(ftree, A[i], ed_len[i])
max_len = max(st_len)
st_cnt_len = [0 for i in range(N + 1)]
for i in range(N):
	if ed_len[i] + st_len[i] - 1 == max_len:
		st_cnt_len[st_len[i]] += 1
for i in range(N):
	if ed_len[i] + st_len[i] - 1 != max_len:
		print(1, end='')
	elif st_cnt_len[st_len[i]] > 1:
		print(2, end='')
	else:
		print(3, end='')
print()


import bisect
import sys
MAX_N = 1000000
from bisect import *

def LIS(arr):
	d = [0] * n
	last = []
	for i in range(n):
		if not last or last[-1] < arr[i]:
			last.append(arr[i])
		idx = bisect_left(last, arr[i])
		last[idx] = arr[i]
		d[i] = idx + 1
	return d
n = int(input())
a = list(map(int, input().split()))
Order_d = LIS(a)
b = [-v for v in a]
b.reverse()
Reverse_d = LIS(b)
Reverse_d.reverse()
Lis = max(Order_d)
ans = [1] * n
for i in range(n):
	if Order_d[i] + Reverse_d[i] == Lis + 1:
		ans[i] = 3
Lmax = -10000000000.0
Rmin = 10000000000.0
for i in range(n):
	if ans[i] == 1:
		continue
	if a[i] <= Lmax:
		ans[i] = 2
	Lmax = max(Lmax, a[i])
for i in range(n - 1, -1, -1):
	if ans[i] == 1:
		continue
	if a[i] >= Rmin:
		ans[i] = 2
	Rmin = min(Rmin, a[i])
first_Lis_idx = 0
second_Lis_idx = 0
for i in range(n):
	if ans[i] == 3:
		first_Lis_idx = i
		break
for i in range(n - 1, -1, -1):
	if ans[i] == 3:
		second_Lis_idx = i
		break
for v in ans:
	print(v, end='')


import sys
import re
import collections
import threading
import bisect
N = 0
Last = []
AA = [0 for _ in range(100005)]
LL = [0 for _ in range(100005)]
BB = [0 for _ in range(100005)]
SS = [0 for _ in range(100005)]
TT = [0 for _ in range(100005)]
ANS = [1 for _ in range(100005)]

def LIS(A, L):
	global N
	Last.append(-1)
	for i in range(N):
		if Last[-1] < A[i]:
			Last.append(A[i])
		it = bisect.bisect_left(Last, A[i])
		Last[it] = A[i]
		L[i] = it
N = int(sys.stdin.readline())
AA = list(map(int, sys.stdin.readline().strip().split()))
LIS(AA, LL)
length = max(LL)
for i in range(N):
	BB[N - i - 1] = 1000000 - AA[i]
Last = []
LIS(BB, SS)
for i in range(N):
	TT[N - i - 1] = SS[i]
for i in range(N):
	if LL[i] + TT[i] == length + 1:
		ANS[i] = 3
maxi = 0
mini = 1000000
for i in range(N):
	if ANS[i] != 1:
		if AA[i] <= maxi:
			ANS[i] = 2
		maxi = max(maxi, AA[i])
for i in range(N - 1, -1, -1):
	if ANS[i] != 1:
		if AA[i] >= mini:
			ANS[i] = 2
		mini = min(mini, AA[i])
for i in range(N):
	print(ANS[i], end='', flush=True)
print()