Chef and Rainbow Array

Link to problem here.

Chef likes all arrays equally. But he likes some arrays more equally than others. In particular, he loves Rainbow Arrays.

An array is Rainbow if it has the following structure:

• First a₁ elements equal 1.
• Next a₂ elements equal 2.
• Next a₃ elements equal 3.
• Next a₄ elements equal 4.
• Next a₅ elements equal 5.
• Next a₆ elements equal 6.
• Next a₇ elements equal 7.
• Next a₆ elements equal 6.
• Next a₅ elements equal 5.
• Next a₄ elements equal 4.
• Next a₃ elements equal 3.
• Next a₂ elements equal 2.
• Next a₁ elements equal 1.
• a_i can be any non-zero positive integer.
• There are no other elements in array.

Help Chef in finding out if the given array is a Rainbow Array or not.

Input

• The first line of the input contains an integer T denoting the number of test cases.
• The first line of each test case contains an integer N, denoting the number of elements in the given array.
• The second line contains N space-separated integers A₁, A₂, ..., A_N denoting the elements of array.

Output

• For each test case, output a line containing "yes" or "no" (without quotes) corresponding to the case if the array is rainbow array or not.

Constraints

• 1 ≤ T ≤ 100
• 7 ≤ N ≤ 100
• 1 ≤ A_i ≤ 10

Subtasks

• Subtask 1 (100 points) : Original constraints

Example

Input
3
19
1 2 3 4 4 5 6 6 6 7 6 6 6 5 4 4 3 2 1
14
1 2 3 4 5 6 7 6 5 4 3 2 1 1
13
1 2 3 4 5 6 8 6 5 4 3 2 1

Output
yes
no
no

Explanation

The first example satisfies all the conditions.

The second example has 1 element of value 1 at the beginning and 2 elements of value 1 at the end.

The third one has no elements with value 7 after elements with value 6.

Problem Solving 

• This seems to be a palindrome problem. 
• However this is incorrect, the input is mean to have increment by 1 at each step.
• Following from that one can clearly see that the N should be odd to satisfy these properties. 
• This gives us an early exit the range of values are small and we do not have to perform any operation other than comparison. So overflow is not possible.
• For space we need to store at least half of the array before we can start comparing the other half.
• A Stack looks to be more suitable for this problem. But we will implement an Stack later in syllabus under that section. 
• We can also carefully implement this recursively and use the native stack space instead of allocating memory ourselves. 
• One more issue here is that the size of the array should be decided at run time, which our array cannot do so we have to use a vector data structure, as discussed in previous post.
• Okay, So the submission went unsuccessful here. 
• It gives TLE, that means there is unseen problem that I have missed. 
• Okay so I found the glitch and solved it here, The problem was we were contructing the vector with N/2 capacity but then pushing back instead of using the allocated memory which for bigger inputs caused bad::alloc(). However it now says Wrong Answer. 
• Okay realized that we can ignore N < 3. checking for more ideas.
• Okay so misinterpreted the problem itself, the numbers appears to have meant that the numbers should grow up to 7 and come back to 1. In our case we just checked whether the numbers are increasing first and then decreasing to form a palindrome. 
• Okay so I submitted another solution which passed half of the task, one still remaining. I just capped my approach up to 7. Submission here. 
• Also that N < 3 should be changed to N < 13. Submission here
• After successive failures and beating up confidence to this "CAKEWALK" difficulty, I thought that I am just trying to fix my solution even after the original solution I wrote was thinking about misinterpreted problem. 
• So I wrote from scratch again, this time I created state machines, basically two functions one which validates increasing values till mid array and the other which validates decreasing through rest of the array. Through the traversal we keep the count of 1-7 numbers and while decreasing we keep decrement the count so that while changing the number or in the end the count should be 0. 
• Also learned, that std::array does not create zero initialized array - use array.fill to do that. here
• After few off by 1 errors and edge cases, this submission went through here. 
• Also learned that premature optimizations really bite in the ass if you are actively modifying the code. 
• This problem was easy to think, difficult to code and hard to interpret correctly. 
• In the end, this problem was easily solved by arrays only no vector required.