A marching band director lines up n performers in a single file, left to right. Each performer wears a festival badge showing a positive integer. The director wants to slice the line into consecutive formation blocks so that every performer belongs to exactly one block, and each block must be one of exactly three kinds:
Determine whether the entire line can be partitioned into such blocks with nobody left over.
Print YES if the whole line can be partitioned into twin, triplet, and/or step blocks as described, otherwise print NO.
Example 1
Input
5 4 4 4 5 6
Expected
YES
Explanation
Split the line into a twin block (4, 4) followed by a step block (4, 5, 6), which increases by exactly 1 each step. Both blocks are valid and together cover all 5 performers, so the answer is YES.
Example 2
Input
4 1 2 3 4
Expected
NO
Explanation
The only 3-performer block that works at the start is the step block (1, 2, 3), but that leaves performer 4 alone, and a block of size 1 is not allowed. No twin block works either, since badge 1 and badge 2 differ. No partition covers all 4 performers, so the answer is NO.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →