Array Construction
Basics of hash tables
Data structures
Hash tables
42.0% success
2,643 attempts
1.5s time
256MB memory
1024KB max code

You are given two arrays \(a = [a_1, a_2, ..., a_n]\) and \(b = [b_1, b_2, ..., b_n]\), with \(a_1 = a_2 = ... = a_n = 0\).

First, you must choose two of indices \(i, j\) (\(1 \leq i, j \leq n, i \neq j\)) and assign \(a_i = a_j = 1\).

Then perform the following operation as many times as you want:

  • Choose an index \(k (1 \leq k \leq n)\), and add the product of the two largest integers in \(a\) to \(a_k\). That is, \(a_k = a_k + a_i \cdot a_j\), where \(a_i \geq a_j \geq a_l\) for all \(l (1 \leq l \leq n, l \neq i, l \neq j)\).

Now, determine if you can transform the array \(a\) into the array \(b\) or not.

If you can construct the array, then print “YES”. Otherwise, print “NO”.

Constraints

  • \(1 \leq T \leq 1000\)
  • \(2 \leq n \leq 10^5\)
  • \(0 \leq b_i \leq 10^9\)

Input Format

  • The first line contains a single integer \(T\) —- the number of test cases.
  • For each testcase:
    • The first line contains one integer \(n\) —- the length of the arrays.
    • The second line contains \(n\) nonnegative integers \(b_1, b_2, ... , b_n\).
  • The sum of \(n\) over all test cases does not exceed \(10^6\).

Output Format

  • For each Testcase, output "YES" if the array \(a\) can be transformed into \(b\). Otherwise, output "NO".
Examples
Input
3
4
8 1 0 0
4
5 2 2 0
4
6 3 0 0
Output
YES
YES
NO
Explanation

In the first case:

  • \(a = [0,0,0, 0]\) initially.
  • Assign \(a_1 = a_2 = 1\), so \(a = [1, 1, 0, 0]\).
  • Operation with \(k = 1\), after the opertaion \(a = [2, 1, 0, 0]\).

  • Operation with \(k = 1\), after the opertaion \(a = [4, 1, 0, 0]\).

  • Operation with \(k = 1\), after the opertaion \(a = [8, 1, 0, 0]\).

In the second case:

  • \(a = [0,0,0, 0]\) initially.
  • Assign \(a_1 = a_2 = 1\), so \(a = [1, 1, 0, 0]\).
  • Operation with \(k = 2\), after the opertaion \(a = [1, 2, 0, 0]\).

  • Operation with \(k = 3\), after the opertaion \(a = [1, 2, 2, 0]\).

  • Operation with \(k = 1\), after the opertaion \(a = [5, 2, 2, 0]\).

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading Editor...