You are given a long decimal number $a$ consisting of $n$ digits from $1$ to $9$. You also have a function $f$ that maps every digit from $1$ to $9$ to some (possibly the same) digit from $1$ to $9$.

You can perform the following operation no more than once: choose a non-empty contiguous subsegment of digits in $a$, and replace each digit $x$ from this segment with $f(x)$. For example, if $a = 1337$, $f(1) = 1$, $f(3) = 5$, $f(7) = 3$, and you choose the segment consisting of three rightmost digits, you get $1553$ as the result.

What is the maximum possible number you can obtain applying this operation no more than once?


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of digits in $a$.

The second line contains a string of $n$ characters, denoting the number $a$. Each character is a decimal digit from $1$ to $9$.

The third line contains exactly $9$ integers $f(1)$, $f(2)$, ..., $f(9)$ ($1 \le f(i) \le 9$).


-----Output-----

Print the maximum number you can get after applying the operation described in the statement no more than once.


-----Examples-----
Input
4
1337
1 2 5 4 6 6 3 1 9

Output
1557

Input
5
11111
9 8 7 6 5 4 3 2 1

Output
99999

Input
2
33
1 1 1 1 1 1 1 1 1

Output
33

Difficulty: introductory

Starter code:

Solutions:
def main():
    n = int(input())
    a = list(map(int, input()))
    f = [0] + list(map(int, input().split()))
    i = 0
    while f[a[i]] <= a[i]:
        i += 1
        if i == n:
            break
    for j in range(i, n):
        if f[a[j]] < a[j]:
            break
        else:
            a[j] = f[a[j]]
    print("".join(str(x) for x in a))
    return 0

main()

n = int(input())
s = input()
d = input().split()
x = 0
for i in s:
    if d[int(i) - 1] > i:
        break
    x += 1
r = s[:x]
p = x
for i in s[x:]:
    if d[int(i) - 1] >= i:
        r += d[int(i) - 1]
    else:
        r += s[p:]
        break
    p += 1
print(r)

# AC
import sys


class Main:
    def __init__(self):
        self.buff = None
        self.index = 0

    def __next__(self):
        if self.buff is None or self.index == len(self.buff):
            self.buff = sys.stdin.readline().split()
            self.index = 0
        val = self.buff[self.index]
        self.index += 1
        return val

    def next_int(self):
        return int(next(self))

    def solve(self):
        n = self.next_int()
        s = [int(x) for x in next(self)]
        x = [self.next_int() for _ in range(0, 9)]
        id = 0
        while id < n and s[id] >= x[s[id] - 1]:
            id += 1
        while id < n and s[id] <= x[s[id] - 1]:
            s[id] = x[s[id] - 1]
            id += 1
        print(''.join([str(x) for x in s]))


def __starting_point():
    Main().solve()

__starting_point()

def main():
    input()
    n = [int(x) for x in input()]
    f = [0]+[int(x) for x in input().split()]
    for i in range(len(n)):
        if f[n[i]] > n[i]:
            n[i] = f[n[i]]
            for j in range(i+1, len(n)):
                if f[n[j]] < n[j]:
                    break
                n[j] = f[n[j]]
            break
    print(''.join(str(x) for x in n))
main()



n = int(input())
a = list(input())
fi = list(map(int,input().split()))
flag = 0
for i in range(n):
    if fi[int(a[i])-1] > int(a[i]) and flag != 2:
        flag = 1
        print(fi[int(a[i])-1],end="")
    elif fi[int(a[i])-1] == int(a[i]) and flag == 1:
        print(a[i],end="")
    else:
        if flag == 1:
            flag = 2
        print(a[i],end="")
    


a = int(input())
N = list(input())
f = list(map(int, input().split()))

ind = 0

for i, n in enumerate(N):
    if int(n) < f[int(n) - 1]:
        N[i] = f[int(n) - 1]
        ind = 1
    if int(n) > f[int(n) - 1] and ind == 1:
        break

print("".join(list(map(str, N))))
        


import sys

input = sys.stdin.readline

n = int(input())

s = [int(x) for x in input().strip()]

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

started = False
for i in range(len(s)):
  if f[s[i]-1] > s[i]:
    started = True
    s[i] = f[s[i]-1]
  elif started and f[s[i]-1] < s[i]:
    break

print(''.join([str(x) for x in s]))


n = int(input())
l = [*map(int, input())]
d = {}
for i, j in enumerate(map(int, input().split())):
    d[i + 1] = j

i = 0
while i < n and d[l[i]] <= l[i]:
    i += 1
while i < n and d[l[i]] >= l[i]:
    l[i] = d[l[i]]
    i += 1
print(''.join(map(str, l)))

#	!/usr/bin/env python3
#	encoding: UTF-8
#	Modified: <26/Apr/2019 08:18:47 PM>


#	✪ H4WK3yE乡
#	Mohd. Farhan Tahir
#	Indian Institute Of Information Technology (IIIT),Gwalior


# ///==========Libraries, Constants and Functions=============///


import sys


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


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


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

# ///==========MAIN=============///


def main():
    n = int(input())
    a = list(input())
    f = get_array()
    flag = False
    for i in range(n):
        x = int(a[i])
        if (x < f[x - 1]):
            flag = True
            a[i] = f[x - 1]
        else:
            if flag == True and x > f[x - 1]:
                break
    print(*a, sep='')


def __starting_point():
    main()

__starting_point()

n = int(input())
a = list(input())
f = list(map(int,input().split()))
f = {i+1:f[i] for i in range(9)}

st = n
for i in range(n):
	c = int(a[i])
	if f[c] > c:
		st = i
		break

for i in range(st,n):
	c = int(a[i])
	if f[c] >= c:
		a[i] = str(f[c])
	else:
		break

print(''.join(a))

n=int(input())
s=str(input())
dict1={}
arr=list(map(int,input().split()))
for i in range(1,10):
	dict1[i]=arr[i-1]
ans=''
i=0
while(i<n):
	if(dict1[int(s[i])]>int(s[i])):
		break
	else:
		ans+=s[i]
		i+=1
#print(ans)
while(i<n):
	if(dict1[int(s[i])]<int(s[i])):
		break
	else:
		ans+=str(dict1[int(s[i])])
		i+=1
ans+=s[i:]
print(ans)



n = int(input())
a1 = list(map(int, list(input())))
u = list(map(int, input().split()))
a2 = []
for i in range(n):
    a2.append(u[a1[i] - 1])
ok = False
i1 = -1
for i in range(n):
    if a2[i] > a1[i]:
        i1 = i
        ok = True
        break
if ok:
    i2 = n
    for i in range(i1 + 1, n):
        if a2[i] < a1[i]:
            i2 = i
            break
    for i in range(i1, i2):
        a1[i] = a2[i]
print(''.join(map(str, a1)))





input()
A = list(map(int,input()))
f = tuple(map(int,input().split()))

for i,a in enumerate(A):
    if a < f[a-1]:
        break
for j,a in enumerate(A[i:], start=i):
    if a > f[a-1]:
        break
    else:
        A[j] = f[a-1]

print(*A, sep='')

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
##################################
# University of Wisconsin-Madison
# Author: Yaqi Zhang
##################################
# This module contains
##################################

# standard library
import sys

def main():
    # nums = list(map(int, input().split()))
    n = int(input())
    s = input()
    assert(len(s) == n)
    digits = list(s)
    m = [0]
    m.extend(list(map(int, input().split())))
    change = False
    for i, ch in enumerate(digits):
        d = int(ch)
        if m[d] > d:
            digits[i] = str(m[d])
            change = True
        else:
            if m[d] < d and change:
                break
    print(''.join(digits))


def __starting_point():
    main()


__starting_point()

n = int(input())
s = list(input())
f = [0] + list(map(int, input().split()))
cok = 1
for i in range(n):
    q = int(s[i])
    if cok:
        if f[q] > q:
            cok = 0
            s[i] = str(f[q])
    else:
        if f[q] >= q:
            s[i] = str(f[q])
        else:
            print(''.join(s))
            return
print(''.join(s))



n=int(input())
num=[int(x) for x in list(input())]
f=[int(x) for x in input().split()]
flag=0
for i in range(n):
    if num[i]<f[num[i]-1]:
        num[i]=f[num[i]-1]
        flag=1
    elif num[i]>f[num[i]-1]:
        if flag==1:
            break
print(*num,sep='')


n = int(input())
s = [int(item) for item in list(input())]
f = [0] + [int(item) for item in input().split()]

new_s = [0] * n
for i in range(n):
    new_s[i] = f[int(s[i])]

i = 0
idx = -1
for j in range(n):
    if new_s[j] > s[j]:
        idx = j
        break

if idx == -1:
    print(''.join(str(item) for item in s))
else:
    start = idx
    while idx < n and new_s[idx] >= s[idx]:
        idx += 1
    u = [str(item) for item in s[:start]]
    v = [str(item) for item in new_s[start:idx]]
    w = [str(item) for item in s[idx:]]
    assert(len(u) + len(v) + len(w) == n)
    print(''.join(u) + ''.join(v) + ''.join(w))


n = int(input())
a = input()

f = [int(x) for x in input().split()]


r = ""

flag = -1
for c in a:

    k = f[int(c)-1]
    if flag == -1:
        if k > int(c):
            flag = 0
            r += str(k)
        else:
            r += c

    elif flag == 0:
        if k < int(c):
            r += c
            flag = 1
        else:
            r += str(k)
    else:
        r += c

print(r)


#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""Codeforces Round #555 (Div. 3)

Problem B. Long Number

:author:         Kitchen Tong
:mail:    kctong529@gmail.com

Please feel free to contact me if you have any question
regarding the implementation below.
"""

__version__ = '0.2'
__date__ = '2019-04-26'

import sys


def solve(a, f):
    mydict = dict(list(zip(list(map(str, list(range(1, 10)))), f)))
    ans = []
    flag = -1
    for ch in a:
        if mydict[ch] > ch and flag <= 0:
            ans.append(mydict[ch])
            flag = 0
        else:
            ans.append(ch)
            if flag >= 0 and mydict[ch] < ch:
                flag = 1
    return ''.join(ans)

def main(argv=None):
    n = int(input())
    a = list(input())
    f = list(input().split())
    print(solve(a, f))
    return 0

def __starting_point():
    STATUS = main()
    return(STATUS)


__starting_point()

n = int(input())
a = list(input())
d = dict()
s = input().split()
can = set()
for i in range(9):
    if i < int(s[i]):
        can.add(str(i + 1))
    d[str(i + 1)] = s[i]
for i in range(n):
    if a[i] < d[a[i]]:
        a[i] = d[a[i]]
        i += 1
        while i < n and a[i] in can:
            a[i] = d[a[i]]
            i += 1
        break
print(*a, sep='')


n = int(input())
x = list(input())
f = dict(zip(range(1,10), map(int, input().strip().split())))

for i in range(n):
    p = int(x[i])
    if p<f[p]:
        while i<n and int(x[i])<=f[int(x[i])]:
            x[i] = str(f[int(x[i])])
            i += 1
        break
print("".join(x))

n = int(input())
s = input()
perm = list(map(int,input().split()))
wyn = list(map(int,s))
c = 0
for i in range(n):
	if c == 1:
		break
	if perm[int(s[i])-1] > int(s[i]):
		wyn[i] = perm[int(s[i])-1]
		j = i 
		c = 1
		while True:
			j += 1
			if j < n and perm[int(s[j])-1] >= int(s[j]):
					wyn[j] = perm[int(s[j])-1]
			else:
				break
for i in wyn:
	print(i, end = "")

n = int(input())
s = list(input())
f = [int(elem) for elem in input().split()]
ind = -1
for i in range(n):
    if f[int(s[i]) - 1] > int(s[i]):
        ind = i
        break
if ind == -1:
    for i in range(n):
        print(s[i], end='')
else:
    x = i
    while x < n and f[int(s[x]) - 1] >= int(s[x]):
        s[x] = f[int(s[x]) - 1]
        x += 1
    for i in range(n):
        print(s[i], end='')

n = int(input())
a = list(input())

f = ['0']
f.extend(list(input().split()))
# print('f:', f)

started = False
for i, item in enumerate(a):
	if not started:
		if int(f[int(item)]) > int(item):
			a[i] = f[int(item)]
			started = True
	else:
		if int(f[int(item)]) >= int(item):
			a[i] = f[int(item)]
		else:
			break

print(''.join(a))


n = int(input())
a = input()
sp = list(map(str, input().split()))
new = ""
fl1 = True
fl2 = False
for x in a:
	if int(x) > int(sp[int(x) - 1]) and not fl1 or fl2:
		fl2 = True
		new += x
	else:
		if int(x) < int(sp[int(x) - 1]):
			new += sp[int(x) - 1]
			fl1 = False
		else:
			new += x
print(new)