Difference Operations Solution Codeforces

Table of Contents

Difference Operations Solution Codeforces

You are given an array aa consisting of nn positive integers.

You are allowed to perform this operation any number of times (possibly, zero):

  • choose an index ii (2in2≤i≤n), and change aiai to aiai1ai−ai−1.

Is it possible to make ai=0ai=0 for all 2in2≤i≤n?

Input Difference Operations Solution Codeforces

The input consists of multiple test cases. The first line contains a single integer tt (1t1001≤t≤100)  — the number of test cases. The description of the test cases follows.

The first line contains one integer nn (2n1002≤n≤100) — the length of array aa.

The second line contains nn integers a1,a2,,ana1,a2,…,an (1ai1091≤ai≤109).

Output Difference Operations Solution Codeforces

For each test case, print “YES” (without quotes), if it is possible to change aiai to 00 for all 2in2≤i≤n, and “NO” (without quotes) otherwise.

You can print letters in any case (upper or lower).

Example
input

Copy
4
2
5 10
3
1 2 3
4
1 1 1 1
9
9 9 8 2 4 4 3 5 3

output Difference Operations Solution Codeforces

Copy

YES
YES
YES
NO

Note Difference Operations Solution Codeforces

In the first test case, the initial array is [5,10][5,10]. You can perform 22 operations to reach the goal:

  1. Choose i=2i=2, and the array becomes [5,5][5,5].
  2. Choose i=2i=2, and the array becomes [5,0][5,0].

In the second test case, the initial array is [1,2,3][1,2,3]. You can perform 44 operations to reach the goal:

  1. Choose i=3i=3, and the array becomes [1,2,1][1,2,1].
  2. Choose i=2i=2, and the array becomes [1,1,1][1,1,1].
  3. Choose i=3i=3, and the array becomes [1,1,0][1,1,0].
  4. Choose i=2i=2, and the array becomes [1,0,0][1,0,0].

In the third test case, you can choose indices in the order 443322.

For Solution

Click Here

Leave a Comment