Mark the Dust Sweeper solution codeforces

Mark the Dust Sweeper solution codeforces

Solution – CLICK HERE

Mark is cleaning a row of n rooms. The i-th room has a nonnegative dust level ai. He has a magical cleaning machine that can do the following three-step operation.

  • Select two indices <i<j such that the dust levels ai+1ai+11aj−1 are all strictly greater than 00.
  • Set ai to 1ai−1.
  • Set aj to +1aj+1.

Mark’s goal is to make 1=2==1=0a1=a2=…=an−1=0 so that he can nicely sweep the n-th room. Determine the minimum number of operations needed to reach his goal.

Input

Mark the Dust Sweeper solution codeforces

The first line contains a single integer t (11041≤t≤104) — the number of test cases.

The first line of each test case contains a single integer n (221052≤n≤2⋅105) — the number of rooms.

The second line of each test case contains n integers 1a12a2, …, an (01090≤ai≤109) — the dust level of each room.

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

Output

Mark the Dust Sweeper solution codeforces

For each test case, print a line containing a single integer — the minimum number of operations. It can be proven that there is a sequence of operations that meets the goal.

Example

input

Copy
4
3
2 0 0
5
0 2 0 2 0
6
2 0 3 0 4 6
4
0 0 0 10

output

Copy
3
5
11
0
Note

Mark the Dust Sweeper solution codeforces

In the first case, one possible sequence of operations is as follows.

  • Choose =1i=1 and =2j=2, yielding the array [1,1,0][1,1,0].
  • Choose =1i=1 and =3j=3, yielding the array [0,1,1][0,1,1].
  • Choose =2i=2 and =3j=3, yielding the array [0,0,2][0,0,2].

At this point, 1=2=0a1=a2=0, completing the process.In the second case, one possible sequence of operations is as follows.

  • Choose =4i=4 and =5j=5, yielding the array [0,2,0,1,1][0,2,0,1,1].
  • Choose =2i=2 and =3j=3, yielding the array [0,1,1,1,1][0,1,1,1,1].
  • Choose =2i=2 and =5j=5, yielding the array [0,0,1,1,2][0,0,1,1,2].
  • Choose =3i=3 and =5j=5, yielding the array [0,0,0,1,3][0,0,0,1,3].
  • Choose =4i=4 and =5j=5, yielding the array [0,0,0,0,4][0,0,0,0,4].

In the last case, the array already satisfies the condition.

Leave a Comment

Your email address will not be published.