There are stacks of blocks in a row. You are given an array , where is the initial height of the -th stack.
Every second, each nonempty stack whose height is strictly greater than the height of at least one of its immediate neighbours loses exactly one block. The positions immediately outside the row have height zero.
All comparisons use the heights at the beginning of the second, and all changes happen simultaneously. Empty stacks remain in their original positions and have height zero.
For each test case, find the number of seconds until every stack is empty.
All three stacks lose a block in the first second. The two outer stacks become empty, and the middle stack keeps losing one block per second until it becomes empty after seconds.
The heights change as follows: . Therefore, the answer is .
The only stack has height and a zero-height neighbour outside the row, so it loses one block every second and becomes empty after seconds.
The heights change as follows: . Therefore, the answer is .
During the first three seconds, only the two outer stacks lose blocks. All five heights are then . It takes three more seconds for every stack to become empty, so the answer is .