[Solution] Sending a Sequence Over the Network solution codeforces

Table of Contents

Sending a Sequence Over the Network solution codeforces

Sending a Sequence Over the Network solution codeforces – 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.

[Solution] Sending a Sequence Over the Network solution codeforces

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𝑡1041≤t≤104) — the number of test cases.

Each test case consists of two lines.

The first line of the test case contains an integer 𝑛n (1𝑛21051≤n≤2⋅105) — the size of the sequence 𝑏b.

The second line of test case contains 𝑛n integers 𝑏1,𝑏2,,𝑏𝑛b1,b2,…,bn (1𝑏𝑖1091≤bi≤109) — the sequence 𝑏b itself.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 21052⋅105.

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 yEsyesYes and YES will be recognized as positive response).

[Solution] Sending a Sequence Over the Network solution codeforces

input

Copy
7
9
1 1 2 3 1 3 2 2 3
5
12 1 2 7 5
6
5 7 8 9 10 3
4
4 8 6 2
2
3 1
10
4 6 2 1 9 4 9 3 4 2
1
1

output

Copy
YES
YES
YES
NO
YES
YES
NO

[Solution] Sending a Sequence Over the Network solution codeforces

In the first case, the sequence 𝑏b could be obtained from the sequence 𝑎=[1,2,3,1,2,3]a=[1,2,3,1,2,3] with the following partition: [1]+[2,3,1]+[2,3][1]+[2,3,1]+[2,3]. The sequence 𝑏b[1,1,2,3,1,3,2,2,3][1,1,2,3,1,3,2,2,3].

In the second case, the sequence 𝑏b could be obtained from the sequence 𝑎=[12,7,5]a=[12,7,5] with the following partition: [12]+[7,5][12]+[7,5]. The sequence 𝑏b[12,1,2,7,5][12,1,2,7,5].

In the third case, the sequence 𝑏b could be obtained from the sequence 𝑎=[7,8,9,10,3]a=[7,8,9,10,3] with the following partition: [7,8,9,10,3][7,8,9,10,3]. The sequence 𝑏b[5,7,8,9,10,3][5,7,8,9,10,3].

In the fourth case, there is no sequence 𝑎a such that changing 𝑎a for transmission over the network could produce a sequence 𝑏b.

Leave a Comment