Recently, Chef has noticed that he is becoming fatter than ever. It is not surprising, as Chef is eating a lot of the food he is cooking. Therefore, he has been doing exercises for the last $N$ days (numbered $1$ through $N$). For some of these days, Chef remembers for how many minutes he exercised. You are given a sequence $A_{1}, A_{2}, \ldots, A_{N}$. For each valid $i$, if $A_{i} ≥ 0$, then Chef exercised for $A_{i}$ minutes on the $i$-th day; otherwise, Chef forgot how long he exercised on the $i$-th day and $A_{i} = -1$. Note that Chef could only have exercised for an integer non-negative number of minutes on each day, including the days he does not remember.

Chef can also compare how long he exercised on each two consecutive days. You are given a string $S$ with length $N-1$. For each valid $i$, the $i$-th character of $S$ is one of the following:
'>' if Chef exercised for strictly more minutes on the $i$-th day than on the $(i+1)$-th day
'=' if Chef exercised for an equally long time on the $i$-th day and on the $(i+1)$-th day
'<' if Chef exercised for strictly more minutes on the $(i+1)$-th day than on the $i$-th day

Chef is doubting his memory, so he wants you to check if the information is consistent, i.e. if there is a way to determine for how many minutes Chef exercised on each day he does not remember such that the string $S$ describes the correct comparison operators.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.
The third line contains a single string $S$.

------  Output ------
For each test case, if the information on the input is inconsistent, print a single line containing the string "NO", otherwise output  "YES"

------  Constraints  ------
$1 ≤ T ≤ 1,000$
$2 ≤ N ≤ 10^{5}$
$-1 ≤ A_{i} ≤ 10^{6}$ for each valid $i$
$|S| = N-1$
$S$ contains only characters '' and '='
for each valid $i$, if $A_{i} \neq -1$ and $A_{i+1} \neq -1$, then the $i$-th character of $S$ is consistent with $A_{i}$ and $A_{i+1}$
the sum of $N$ over all test cases does not exceed $10^{6}$

----- Sample Input 1 ------ 
5

6

7 5 -1 -1 -1 10

>≥>>

6

7 5 -1 -1 -1 10

>≥

2

0 -1

>

5

5 -1 -1 -1 10

<<<<

5

5 -1 -1 -1 8

<<<<
----- Sample Output 1 ------ 
NO

YES

NO

YES

NO
----- explanation 1 ------ 
Example case 1: The number of minutes Chef spent exercising on day $5$ must be bigger than $10$ and smaller than $5$, which is impossible.

Example case 3: Chef must have exercised for a negative number of minutes on day $2$, which is not allowed.

Example case 5: The information is inconsistent because Chef only exercises for an integer number of minutes on each day. Since the number of minutes he spent exercising on each day must be increasing, he must have spent at least $6$ minutes on day $2$, at least $7$ minutes on day $3$, at least $8$ on day $4$ and at least $9$ on day $5$, but $A_{5} = 8$.

Difficulty: VERY_HARD
Tags: Constructive algorithms

Implementation

Ad-hoc

Starter code:

Solutions:
t = int(input())
while t:
	n = int(input())
	A = list(map(int, input().split()))
	S = input()
	if A[0] == -1:
		min = 0
		max = 9999999999
	else:
		min = A[0]
		max = A[0]
	ans = 'YES'
	for i in range(1, n):
		if A[i] == -1:
			if S[i - 1] == '<':
				min = min + 1
				max = 9999999999
			elif S[i - 1] == '>':
				min = 0
				max = max - 1
		elif S[i - 1] == '<':
			if A[i] >= min + 1:
				min = A[i]
				max = A[i]
			else:
				ans = 'NO'
				break
		elif S[i - 1] == '>':
			if A[i] <= max - 1:
				min = A[i]
				max = A[i]
			else:
				ans = 'NO'
				break
		elif min <= A[i] <= max:
			min = A[i]
			max = A[i]
		else:
			ans = 'NO'
			break
		if min > max:
			ans = 'NO'
			break
	print(ans)
	t -= 1


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	S = input()
	if A[0] == -1:
		mn = 0
		mx = 999999999
	else:
		mn = A[0]
		mx = A[0]
	ans = 'YES'
	for i in range(1, N):
		if A[i] == -1:
			if S[i - 1] == '>':
				mn = 0
				mx = mx - 1
			elif S[i - 1] == '<':
				mn += 1
				mx = 999999999
		elif S[i - 1] == '>':
			if A[i] <= mx - 1:
				mn = A[i]
				mx = A[i]
			else:
				ans = 'NO'
				break
		elif S[i - 1] == '<':
			if mn + 1 <= A[i]:
				mn = A[i]
				mx = A[i]
			else:
				ans = 'NO'
				break
		elif mn <= A[i] <= mx:
			mn = A[i]
			mx = A[i]
		else:
			ans = 'NO'
			break
		if mn > mx:
			ans = 'NO'
			break
	print(ans)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	s = sys.stdin.readline().strip()
	(mn, mx) = (0, pow(10, 7))
	i = 1
	while i < n:
		if s[i - 1] == '<':
			if a[i - 1] != -1:
				mn = a[i - 1] + 1
			else:
				mn = mn + 1
			mx = pow(10, 7)
		elif s[i - 1] == '>':
			if a[i - 1] != -1:
				mx = a[i - 1] - 1
			else:
				mx = mx - 1
			mn = 0
		elif a[i - 1] != -1:
			mx = mn = a[i - 1]
		if mx < 0:
			break
		if a[i] != -1 and (a[i] < mn or a[i] > mx):
			break
		i += 1
	if i == n:
		print('YES')
	else:
		print('NO')


t = int(input())
for ankit in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = input()
	f = 0
	mi = 0
	ma = 10000000000
	for i in range(n - 1):
		if a[i] != -1:
			if a[i] >= mi and a[i] <= ma:
				f = 0
			else:
				f = 1
				break
			if b[i] == '<':
				mi = a[i] + 1
				ma = 10000000000
			elif b[i] == '>':
				ma = a[i] - 1
				mi = 0
			else:
				mi = a[i]
				ma = a[i]
		elif b[i] == '<':
			mi += 1
			ma = 10000000000
		elif b[i] == '>':
			ma -= 1
			mi = 0
		else:
			mi = mi
			ma = ma
		if ma < 0 or ma < mi:
			f = 1
			break
	if a[n - 1] != -1:
		if f == 0 and a[n - 1] >= mi and (a[n - 1] <= ma):
			f = 0
		else:
			f = 1
	print('YES') if f == 0 else print('NO')


t = int(input(''))
import math
for v in range(t):
	n = int(input(''))
	a = list(map(int, input('').split(' ')))
	s = input('')
	b = []
	res = True
	for i in range(n):
		if a[i] != -1:
			b.append([a[i], a[i]])
		else:
			b.append([0, math.inf])
	for i in range(n - 1):
		if s[i] == '>':
			if a[i + 1] == -1:
				b[i + 1][0] = 0
				b[i + 1][1] = b[i][1] - 1
			elif a[i + 1] >= b[i][1]:
				res = False
				break
		if s[i] == '<':
			if a[i + 1] == -1:
				b[i + 1][0] = b[i][0] + 1
				b[i + 1][1] = math.inf
			elif a[i + 1] <= b[i][0]:
				res = False
				break
		if s[i] == '=':
			if a[i + 1] == -1:
				b[i + 1][0] = b[i][0]
				b[i + 1][1] = b[i][1]
			elif a[i + 1] < b[i][0] or a[i + 1] > b[i][1]:
				res = False
				break
		if b[i + 1][1] < b[i + 1][0] or b[i + 1][1] < 0:
			res = False
			break
	if res:
		print('YES')
	else:
		print('NO')