#366 Difference Pyramid

Loading problem...

Preparing the statement, recent submissions, and submit form.

Authors: 2

Statement

Statement language

You are given an array $A=[A_1,A_2,\cdots,A_N]$ of length $N$ , consisting only of $0$ , $1$ , and $2$ .

Repeat the following operation until the length of the array becomes $1$ .

Suppose the current length is $L$ . Construct a new array $B$ of length $L-1$ by

B_i=|A_{i+1}-A_i|\qquad(1\leq i<L),

and replace $A$ with $B$ .

Find the single value that remains at the end.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N$ $A_1\ A_2\ \cdots\ A_N$

For each test case, print the final remaining value on one line.

#	Score	Constraints
1	19	$N\leq2\,000$ . The sum of $N$ over all test cases does not exceed $4\,000$ .
2	33	$A_i\leq1$ ( $1\leq i\leq N$ ).
3	48	No additional constraints.

Input

1
4
0 2 1 0

Output

The array changes as follows.

$0\ 2\ 1\ 0$ $2\ 1\ 1$ $1\ 0$ $1$

Therefore, the final remaining value is $1$ .