You have an array a consisting of n integers. Each integer from 1 to n appears exactly once in this array.

For some indices i (1 ≤ i ≤ n - 1) it is possible to swap i-th element with (i + 1)-th, for other indices it is not possible. You may perform any number of swapping operations any order. There is no limit on the number of times you swap i-th element with (i + 1)-th (if the position is not forbidden).

Can you make this array sorted in ascending order performing some sequence of swapping operations?


-----Input-----

The first line contains one integer n (2 ≤ n ≤ 200000) — the number of elements in the array.

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 200000) — the elements of the array. Each integer from 1 to n appears exactly once.

The third line contains a string of n - 1 characters, each character is either 0 or 1. If i-th character is 1, then you can swap i-th element with (i + 1)-th any number of times, otherwise it is forbidden to swap i-th element with (i + 1)-th.


-----Output-----

If it is possible to sort the array in ascending order using any sequence of swaps you are allowed to make, print YES. Otherwise, print NO.


-----Examples-----
Input
6
1 2 5 3 4 6
01110

Output
YES

Input
6
1 2 5 3 4 6
01010

Output
NO



-----Note-----

In the first example you may swap a_3 and a_4, and then swap a_4 and a_5.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = list(map(int,input().split()))
p = input()
m = 0
suc = True
for i in range(n-1):
    m = max(m,a[i])
    if p[i] == '0' and m>(i+1):
        suc = False
        break
if suc:
    print('YES')
else:
    print('NO')


import getpass
import sys
import math


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


files = True

if getpass.getuser() == 'frohenk' and files:
    sys.stdin = open("test.in")

n = ria()[0]
ar = ria()
st = input()
zer = True
l, r = 0, 0
mx = 0
mn = 200020
changable = [False] * n
for i in range(len(st)):
    if st[i] == '0':

        if not zer:
            if l + 1 > mn or r + 1 < mx:
                print('NO')
                return
        mx = 0
        mn = 200020
        zer = True
        continue
    if zer:
        l = i
    r = i + 1
    mx = max(mx, ar[i])
    mx = max(mx, ar[i + 1])
    mn = min(mn, ar[i])
    mn = min(mn, ar[i + 1])
    changable[i] = True
    changable[i + 1] = True

    zer = False
#print(changable)
for n, i in enumerate(ar):
    if (n + 1) != i and not changable[n]:
        print('NO')
        return
print('YES')



# int(input())
# [int(i) for i in input().split()]

n = int(input())
a = [int(i) for i in input().split()]
ind = [int(i) for i in input()]
ind.append(0)

b = []
curr = 0

for i in range(n):
    if not ind[i]:
        
        tmp = a[curr:i+1]
        tmp.sort()
        b.extend(tmp)
        curr = i + 1

#print(b)
if all(b[i] <= b[i+1] for i in range(n-1)): print("YES")
else: print('NO')



n = int(input())
a = list(map(int, input().split()))
s = input()
sa = sorted(a)
h = {}
for i in range(n):
    h[sa[i]] = i
st = 0
for i in range(n):
    p = i
    ap = h[a[i]]
    if p-ap > st:
        print('NO')
        return
    if i < n-1 and s[i] == '1':
        st += 1
    else:
        st = 0
st = 0
for i in range(n-1, -1, -1):
    if i < n-1 and s[i] == '1':
        st += 1
    else:
        st = 0
    p = i
    ap = h[a[i]]
    if ap - p > st+1:
        print('NO')
        return

print('YES')


n = int(input())
a = list(map(int, input().split()))
s = input()
temp = []
mini = n + 1
maxi = -1
for i in range(n - 1):
    if s[i] == '1':
        mini = min(mini, a[i])
        maxi = max(maxi, a[i])
    elif i != 0 and s[i - 1] == '1':
        mini = min(mini, a[i])
        maxi = max(maxi, a[i])
        temp.append(mini)
        temp.append(maxi)
        mini = n + 1
        maxi = -1
    else:
        temp.append(a[i])
if mini != n + 1:
    mini = min(mini, a[-1])
    maxi = max(maxi, a[-1])
    temp.append(mini)
    temp.append(maxi)
else:
    temp.append(a[-1])
for i in range(1, len(temp)):
    if temp[i] < temp[i - 1]:
        print('NO')
        break
else:
    print('YES')


def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    s = input()
    
    xx = sorted( (a[i], i) for i in range(n) )
    oo = [-1] * n
    for i in range(n):
        oo[xx[i][1]] = i
    
    #print(a)    
    #print(oo)
    
    nn = -1
    for i in range(n):
        nn = max(nn, oo[i])
        if i < nn and s[i]=='0':
            print("NO")
            break
    else:
        print("YES")
    
    
def __starting_point():
    main()

__starting_point()

def check(vals, allowed):
    groups = []
    group = []
    for v, b in zip(vals, allowed):
        group.append(v)
        if b == '0':
            group.sort()
            groups.append(group)
            group = []
    flat = [v for group in groups for v in group]

    for i in range(1, len(flat)):
        if flat[i] < flat[i - 1]:
            return False
    return True

n = int(input())
vals = [int(v) for v in input().split()]
allowed = input().strip() + '0'

print(["NO", "YES"][check(vals, allowed)])


n = int(input())
a = list(map(int, input().split()))
s = list(input())
s.append(1)
rec, q = [], 0
for i in range(n):
    rec.append(q + a[i])
    q = rec[i]
flag = True
for i in range(n):
    if s[i] == "0" and rec[i] > (i + 1) * (i + 2) // 2:
        flag = False
        break

if flag:
    print("YES")
else:
    print("NO")

N = int(input())

T = [0]*(N+1)

for i,j in enumerate(map(int,input().split())):
  j -= 1
  if i > j:
    i,j = j,i
  T[i] += 1
  T[j] -= 1

from itertools import accumulate
T = list(accumulate(T))
T.pop()


for i,j in zip(map(int, input()), T):
  if j != 0 and i == 0:
    print('NO')
    return

print('YES')

n = int(input())
a = list(map(int, input().split()))
s = input()
d = []
cl = 0
mi = 0
i = 0
while i < len(s):
	while i < len(s) and s[i] == "1":
		i += 1
		cl += 1
	while i < len(s) and s[i] == "0":
		i += 1
	d.append([mi, cl])
	cl = 0
	mi = i
d.append([n - 1, 1])
if s[-1] != "1":
	d.append([n - 1, 0])
z = []
for i in range(len(d) - 1):
	z += sorted(a[d[i][0]:d[i][1] + d[i][0] + 1])
	z += a[d[i][1] + d[i][0] + 1:d[i + 1][0]]
print("YES" if z == list(range(1, n + 1)) else "NO")

n=int(input())
l=[int(x) for x in input().split()]
s=input()+'0'
i=minn=maxx=0
flag=0
while i<n:
  minn=maxx=l[i]
  start=i+1
  while s[i]!='0':
    minn=min(minn,l[i])
    maxx=max(maxx,l[i])
    i+=1
  minn=min(minn,l[i])
  maxx=max(maxx,l[i])
  end=i+1
  if minn>=start and maxx<=end:
    i+=1
  else:
    flag=1
    break
if flag:
  print("NO")
else:
  print("YES")


length = int(input())
nums = input().split(" ", length - 1)
for i in range(length):
    nums[i] = int(nums[i])
swaps = []
inp = input()
for i in range(length - 1):
    swaps.append(int(inp[i]))

res = 1
currmin = 1
currmax = 1
currnums = [nums[0]]
for i in range(length - 1):
    if swaps[i] == 0:
        currmax = i + 1
        if min(currnums) < currmin or max(currnums) > currmax:
            res = 0
        ##print([currnums, currmax, currmin])
        currmin = i + 2
        currmax = i + 2
        currnums = [nums[i + 1]]
    else:
        currnums.append(nums[i + 1])
        currmax = i + 1
if res == 1:
    print("YES")
else:
    print("NO")


import sys, math, os.path

FILE_INPUT = "c.in"
DEBUG = os.path.isfile(FILE_INPUT)
if DEBUG: 
    sys.stdin = open(FILE_INPUT)    

def ni():
    return map(int, input().split(" "))

def nia(): 
    return list(map(int,input().split()))

def log(x):
    if (DEBUG):
        print(x)

n, = ni()
a = nia()
en = list(map(lambda x: x == '1', input()))

# log(n)
# log(a)
# log(en)

count = 1
i = 0
while (i < n-1):
    if (en[i]):
        j = i
        b = [a[i]]
        while (j < n-1 and en[j]):
            j += 1
            b.append(a[j])
        b.sort()
        # log(b)
        for j in b:
            if (j != count):
                print("NO")
                return
            else:
                count += 1    
        i = j        
    else:
        if (a[i] == count):
            count += 1
        else:
            print("NO")
            return
        i += 1
    

print("YES")

import sys, math, os.path

FILE_INPUT = "c.in"
DEBUG = os.path.isfile(FILE_INPUT)
if DEBUG: 
    sys.stdin = open(FILE_INPUT)    

def ni():
    return map(int, input().split(" "))

def nia(): 
    return list(map(int,input().split()))

def log(x):
    if (DEBUG):
        print(x)

n, = ni()
a = nia()
en = list(map(lambda x: x == '1', input()))

# log(n)
# log(a)
# log(en)

count = 1
i = 0
while (i < n-1):
    if (en[i]):
        j = i
        b = [a[i]]
        while (j < n-1 and en[j]):
            j += 1
            b.append(a[j])
        b.sort()
        # log(b)
        for j in b:
            if (j != count):
                print("NO")
                return
            else:
                count += 1    
        i = j        
    else:
        if (a[i] == count):
            count += 1
        else:
            print("NO")
            return
        i += 1
    

print("YES")

# C

n = int(input())
A = list(map(int, input().split()))
flag = input()

zero_flag = []
for i in range(n-1):
    if flag[i] == "0":
        zero_flag.append(i)

for i in range(len(zero_flag)):
    if i == len(zero_flag) - 1:
        if set(A[zero_flag[i]+1:]) != set(range(zero_flag[i]+2, n+1)):
            print("NO")
            quit()
    elif i == 0:
        if set(A[:zero_flag[i]+1]) != set(range(1, zero_flag[i]+2)):
            print("NO")
            quit()
    else:
        if set(A[zero_flag[i-1]+1:zero_flag[i]+1]) != set(range(zero_flag[i-1]+2, zero_flag[i]+2)):
            print("NO")
            quit()

print("YES")

import sys
n = int(input())

a = list(map(int, input().split()))
s = input()
b = [10**8] * (n+1)

for i in range(len(s)-1, -1, -1):
    b[i] = i if s[i] == '0' else b[i+1]

#print(b)

for i in range(len(a)):
    if a[i] > i + 1:
        if b[i] < a[i]-1:
            print('NO')
            return

print('YES')

import sys, math, os.path

FILE_INPUT = "c.in"
DEBUG = os.path.isfile(FILE_INPUT)
if DEBUG: 
    sys.stdin = open(FILE_INPUT)    

def ni():
    return map(int, input().split(" "))

def nia(): 
    return list(map(int,input().split()))

def log(x):
    if (DEBUG):
        print(x)

n, = ni()
a = nia()
en = list(map(lambda x: x == '1', input()))

# log(n)
# log(a)
# log(en)

# count = 1
i = 0
while (i < n-1):
    if (en[i]):
        j = i
        # b = [a[i]]
        amin = a[i]
        amax = a[i]
        while (j < n-1 and en[j]):
            j += 1
            amin = min(a[j], amin)
            amax = max(a[j], amax)
            # b.append(a[j])
        # b.sort()
        # log(b)
        # for j in b:
        #     if (j != count):
        #         print("NO")
        #         return
        #     else:
        #         count += 1  
        log(f"{i} - {j}")
        if (amin == (i+1) and amax == j+1):
            i = j+1
        else:
            print("NO")
            return
    else:
        # if (a[i] == count):
            # count += 1
        if (a[i] != i+1):
            log(f"{i} != {a[i]}")
            print("NO")
            return
        i += 1
    

print("YES")

import sys, math, os.path

FILE_INPUT = "c.in"
DEBUG = os.path.isfile(FILE_INPUT)
if DEBUG: 
    sys.stdin = open(FILE_INPUT)    

def ni():
    return map(int, input().split(" "))

def nia(): 
    return list(map(int,input().split()))

def log(x):
    if (DEBUG):
        print(x)

n, = ni()
a = nia()
en = list(map(lambda x: x == '1', input()))

# log(n)
# log(a)
# log(en)

# count = 1
i = 0
while (i < n-1):
    if (en[i]):
        j = i
        # b = [a[i]]
        amin = a[i]
        amax = a[i]
        while (j < n-1 and en[j]):
            j += 1
            amin = min(a[j], amin)
            amax = max(a[j], amax)
            # b.append(a[j])
        # b.sort()
        # log(b)
        # for j in b:
        #     if (j != count):
        #         print("NO")
        #         return
        #     else:
        #         count += 1  
        # log(f"{i} - {j}")
        if (amin == (i+1) and amax == (j+1)):
            i = j+1
        else:
            print("NO")
            return
    else:
        # if (a[i] == count):
            # count += 1
        if (a[i] != i+1):
            # log(f"{i} != {a[i]}")
            print("NO")
            return
        i += 1
    

print("YES")

from itertools import groupby

n = int(input())

nums = [int(i) for i in input().split()]
copy = list(nums)

pos = input()


pos = ["".join(g) for k, g in groupby(pos) if k != '#']

#print(pos)

cur_pos = 0

for i in pos:
    if i[0] == '1':
        nums[cur_pos:cur_pos + len(i) + 1] = sorted(nums[cur_pos:cur_pos + len(i) + 1])
    cur_pos += len(i)

if sorted(copy) == nums:
    print("YES")
else:
    print("NO")

n = int(input())
a = list(map(int, input().split()))
s = list([True if x=="1" else False for x in list(input())])
i=0
while i < n:
    if i == n-1:
        if a[-1] != n:
            print("NO")
    elif not s[i]:
        if a[i]-1 != i:
            print("NO")
            return
    else:
        start = i
        i += 1
        while(i < len(s) and s[i]):
            i+=1
        end = i
        test = a[start: end + 1]
        #print([start, end, test])
        if not (max(test) == end + 1 and min(test) == start + 1):
            print("NO")
            return

    i+=1
print("YES")


n = int(input())
s = input().split()
arr = []
for l in s:
    arr.append(int(l))
s = input()
k = len(s)
pos = []
for l in s:
    pos.append(int(l))

i = 0
indexset = set()
valueset = set()
while i < k:
    if pos[i] == 0:
        if arr[i] != i + 1:
            print("NO")
            return

    if pos[i] == 1:
        while i < k:
            if pos[i] == 1:
                indexset.add(i+1)
                valueset.add(arr[i])
                i += 1
            else:
                break
        indexset.add(i+1)
        valueset.add(arr[i])
        if len(indexset ^ valueset) > 0:
            print("NO")
            return
        indexset.clear()
        valueset.clear()

    i += 1
print("YES")


n = int(input())
raw_input = list(map(int, input().split()))
raw_string = input()

supposed_sum = 0
actual_sum = 0

for i in range(1, len(raw_string)+1):
    supposed_sum += i
    actual_sum += raw_input[i-1]
    if raw_string[i-1] == '0':
#        print(i, actual_sum, supposed_sum)
        if actual_sum != supposed_sum:
            print("NO")
            return
        actual_sum = 0
        supposed_sum = 0

print("YES")


n = int(input())
a = [int(x) for x in input().split()]
rot = input()

stack = []
pairs = []
for i in range(len(rot)):
    if rot[i] == '1' and stack == []:
        stack.append(i)
    if rot[i] == '0' and len(stack) > 0:
        stack.append(i-1)
        pairs.append((stack[-2], stack[-1] + 1))
        stack.clear()
if len(stack) > 0:
    pairs.append((stack[-1], n))

for l, r in pairs:
    a[l:r+1] = sorted(a[l:r+1])
##if l != None and r == None:
##    r = len(rot)
##    a[l:r+1] = sorted(a[l:r+1])
print('YNEOS'[not(a == sorted(a))::2])



def can_order(arr, ok):
    i = 0
    while i < len(ok):
        if not ok[i]:
            if i + 1 != arr[i + 1] and (i + 1 >= len(ok) or not ok[i + 1]):
                #print("Not okay and index", i, "==", arr[i])
                return False
            i += 1
        else:
            j = i
            while j < len(ok) and ok[j]:
                j += 1
            if sum(arr[i:j + 1]) != sum(range(i, j + 1)):
                #print(arr[i:j + 1])
                #print("arr[", i, ":", j + 1, "] ==", sum(arr[i:j + 1]))
                #print("sum(range(i, j)) ==", sum(range(i, j + 1)))
                return False
            i = j
    return True


def main():
    N = int(input())
    arr = [int(x) - 1 for x in input().split()]
    ok = [c == '1' for c in input()]
    print("YES" if can_order(arr, ok) else "NO")

def __starting_point():
    main()


__starting_point()

n = int(input())
a = list(map(int, input().split(" ")))
s = list(map(int, input()))
right = [-1] * n
i = n - 2
right[n - 1] = n - 1
if s[i] == 1:
    right[i] = i + 1
else:
    right[i] = i
i -= 1
while i >= 0:
    if s[i] == 0:
        right[i] = i
    else:
        if s[i+1] == 0:
            right[i] = i + 1
        else:
            right[i] = right[i+1]
    i -= 1

ans = True
i = 0
for ai in a:
    if ai - 1 > right[i]:
        ans = False
    i += 1

print("YES" if ans else "NO")