[Solution] Sending a Sequence Over the Network Codeforces Solution

E. Sending a Sequence Over the Network

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

The sequence 𝑎$a$ is sent over the network as follows:

1. sequence 𝑎$a$ is split into segments (each element of the sequence belongs to exactly one segment, each segment is a group of consecutive elements of sequence);
2. for each segment, its length is written next to it, either to the left of it or to the right of it;
3. the resulting sequence 𝑏$b$ is sent over the network.

For example, we needed to send the sequence 𝑎=[1,2,3,1,2,3]$a=[1,2,3,1,2,3]$. Suppose it was split into segments as follows: [1]+[2,3,1]+[2,3]$[1]+[2,3,1]+[2,3]$. Then we could have the following sequences:

• 𝑏=[1,1,3,2,3,1,2,3,2]$b=[1,1,3,2,3,1,2,3,2]$,
• 𝑏=[1,1,3,2,3,1,2,2,3]$b=[1,1,3,2,3,1,2,2,3]$,
• 𝑏=[1,1,2,3,1,3,2,2,3]$b=[1,1,2,3,1,3,2,2,3]$,
• 𝑏=[1,1,2,3,1,3,2,3,2]$b=[1,1,2,3,1,3,2,3,2]$.

If a different segmentation had been used, the sent sequence might have been different.

The sequence 𝑏$b$ is given. Could the sequence 𝑏$b$ be sent over the network? In other words, is there such a sequence 𝑎$a$ that converting 𝑎$a$ to send it over the network could result in a sequence 𝑏$b$?

Input

The first line of input data contains a single integer 𝑡$t$ (1≤𝑡≤104$1\le t\le {10}^4$) — the number of test cases.

Each test case consists of two lines.

The first line of the test case contains an integer 𝑛$n$ (1≤𝑛≤2⋅105$1\le n\le 2\cdot {10}^5$) — the size of the sequence 𝑏$b$.

The second line of test case contains 𝑛$n$ integers 𝑏1,𝑏2,…,𝑏𝑛$b_1,b_2,\dots ,b_n$ (1≤𝑏𝑖≤109$1\le b_i\le {10}^9$) — the sequence 𝑏$b$ itself.

It is guaranteed that the sum of 𝑛$n$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case print on a separate line:

• YES if sequence 𝑏$b$ could be sent over the network, that is, if sequence 𝑏$b$ could be obtained from some sequence 𝑎$a$ to send 𝑎$a$ over the network.
• NO otherwise.

You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as positive response).