Set To Max (Easy Version) (Codeforces 1904D1)
Tags: Greedy, brute force

This is the easy version of the problem. The only differences between the two versions of this problem are the constraints on $$$n$$$ and the time limit. You can make hacks only if all versions of the problem are solved.You are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$.You can perform the following operation some (possibly zero) times:   choose $$$l$$$ and $$$r$$$ such that $$$1 \leq l \leq r \leq n$$$.  let $$$x=\max(a_l,a_{l+1},\ldots,a_r)$$$.  for all $$$l \leq i \leq r$$$, set $$$a_i := x$$$. Determine if you can make array $$$a$$$ equal to array $$$b$$$.

Input: Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the length of the arrays.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of array $$$a$$$.The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) — the elements of array $$$b$$$.It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$10^6$$$.

Output: For each test case, output "YES" (without quotes) if you can make $$$a$$$ into $$$b$$$ using any number of operations, and "NO" (without quotes) otherwise.You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

Note: In the first test case, we can achieve array $$$b$$$ by applying a single operation: $$$(l,r)=(2,3)$$$.In the second test case, it can be shown we cannot achieve array $$$b$$$ in any amount of operations.In the third test case, we can achieve array $$$b$$$ by applying two operations: $$$(l,r)=(2,5)$$$. followed by $$$(l,r)=(1,3)$$$.In the fourth and fifth test cases, it can be shown we cannot achieve array $$$b$$$ in any amount of operations.

Sample Inputs:
5
5
1 2 3 2 4
1 3 3 2 4
5
3 4 2 2 4
3 4 3 4 4
5
3 2 1 1 1
3 3 3 2 2
2
1 1
1 2
3
1 1 2
2 1 2

Sample Outputs:
YES
NO
YES
NO
NO

Solution (Python):
import bisect
from sys import stdin
input = stdin.readline
mod = 10 ** 9 + 7
eps = 10 ** (-9)

def linp(type=int):
    return list(map(type, input().strip().split()))

def minp(type=int):
    return map(type, input().strip().split())

def tinp(type=int):
    return type(input().strip())

def __gcd(a, b):
    return a if b == 0 else __gcd(b, a % b)

def __lcm(a, b):
    return a * b / __gcd(a, b)

def __fact(n):
    return 1 if n == 1 else n * __fact(n - 1)

def __mex(a):
    mex = 0
    a.sort()
    for x in a:
        if x <= mex:
            mex += 1
        else:
            break
    return mex

def __dist(x1, y1, x2, y2):
    return (x1 - x2) ** 2 + (y1 - y2) ** 2

def __getprimes(n):
    isprime = [True for i in range(n + 1)]
    primes = []
    for i in range(2, n + 1):
        if isprime[i]:
            for j in range(i * i, n + 1, i):
                isprime[j] = False
    for i in range(2, n + 1):
        if isprime[i]:
            primes.append(i)
    return primes

def __getdividers(n):
    i = 1
    ret = []
    while i * i <= n:
        if n % i == 0:
            ret.append(i)
            if i * i != n:
                ret.append(n // i)
        i += 1
    ret.sort()
    return ret

def __modInverse(a, m):
    m0 = m
    y = 0
    x = 1
    if m == 1:
        return 0
    while a > 1:
        q = a // m
        t = m
        m = a % m
        a = t
        t = y
        y = x - q * y
        x = t
    if x < 0:
        x = x + m0
    return x

def __isprime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

def __cntprimediv(n):
    ret = 0
    x = n
    i = 2
    while i * i <= x:
        while n % i == 0:
            n //= i
            ret += 1
        i += 1
    if n > 1:
        ret += 1
    return ret

def __primefactors(n):
    ret = []
    x = n
    i = 2
    while i * i <= x:
        while n % i == 0:
            ret.append(i)
            n //= i
        i += 1
    if n > 1:
        ret.append(n)
    return ret

def __sumdigit(n):
    ret = 0
    while n > 0:
        ret += n % 10
        n //= 10
    return ret

def __zfunc(s):
    n = len(s)
    z = [0 for i in range(n)]
    l = 0
    r = 0
    for i in range(1, n):
        if r >= i:
            z[i] = min(z[i - l], r - i + 1)
        while z[i] + i < n and s[z[i]] == s[z[i] + i]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l = i
            r = i + z[i] - 1
    return z

def __to(n, x):
    ret = ''
    while n > 0:
        q = n % x
        if q < 10:
            ret += str(q)
        else:
            ret += chr(q - 10 + ord('a'))
        n //= x
    return ret[::-1]

def solve(t_id):
    n = tinp()
    a = linp()
    b = linp()
    ok = True
    ind = [[] for i in range(n + 1)]
    for i in range(n):
        ind[b[i]].append(i)
    for i in range(1, n + 1):
        for id in ind[i]:
            if a[id] == b[id]:
                continue
            if a[id] > b[id]:
                ok = False
                break
            prev = -1
            ii = id - 1
            while ii >= 0 and a[ii] <= b[ii] and (a[ii] <= b[id]) and (b[id] <= b[ii]):
                if a[ii] == b[id]:
                    prev = ii
                    break
                ii -= 1
            if prev > -1:
                for j in range(prev, id + 1):
                    a[j] = b[id]
            else:
                next = -1
                ii = id + 1
                while ii < n and a[ii] <= b[ii] and (a[ii] <= b[id]) and (b[id] <= b[ii]):
                    if a[ii] == b[id]:
                        next = ii
                        break
                    ii += 1
                if next > -1:
                    for j in range(id, next):
                        a[j] = b[id]
                else:
                    ok = False
                    break
        if not ok:
            break
    for i in range(n):
        if a[i] != b[i]:
            ok = False
    print('YES' if ok else 'NO')
tc = 1
tc = int(input())
for i in range(tc):
    solve(i + 1)

Solution (Python):
from sys import stdin
input = lambda : stdin.buffer.readline().decode().strip()
from collections import deque
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    def solve(order):
        dq = deque()
        for i in order:
            while dq and dq[-1] <= a[i]:
                dq.pop()
            while dq and dq[0] > b[i]:
                dq.popleft()
            dq.append(a[i])
            if dq[0] == b[i]:
                a[i] = b[i]
    solve(range(n))
    solve(reversed(range(n)))
    print('YES' if a == b else 'NO')

Solution (Python):
from sys import stdin
input = lambda : stdin.buffer.readline().decode().strip()
from collections import deque
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    def solve(order):
        dq = deque()
        for i in order:
            while dq and dq[-1] <= a[i]:
                dq.pop()
            while dq and dq[0] > b[i]:
                dq.popleft()
            dq.append(a[i])
            if dq[0] == b[i]:
                a[i] = b[i]
    solve(range(n))
    solve(reversed(range(n)))
    print('YES' if a == b else 'NO')