[Solution] Mark the Dust Sweeper Codeforces Solution

B. Mark the Dust Sweeper

time limit per test

1.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

• Select two indices i<j$i<j$ such that the dust levels ai$a_i$, ai+1$a_{i+1}$, …$\dots$, aj−1$a_{j-1}$ are all strictly greater than 0$0$.
• Set ai$a_i$ to ai−1$a_i-1$.
• Set aj$a_j$ to aj+1$a_j+1$.

Mark's goal is to make a1=a2=…=an−1=0$a_1=a_2=\dots =a_{n-1}=0$ so that he

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

can nicely sweep the n$n$-th room. Determine the minimum number of operations needed to reach his goal.

Input

The first line contains a single integer t$t$ (1≤t≤104$1\le t\le {10}^4$) — the number of test cases.

The first line of each test case contains a single integer n$n$ (2≤n≤2⋅105$2\le n\le 2\cdot {10}^5$) — the number of rooms.

Mark and the Online Exam Codeforces Solution

Mark and Professor Koro Codeforces Solution

Mark and Lightbulbs Codeforces Solution

Mark and His Unfinished Essay Codeforces Solution

Mark the Dust Sweeper Codeforces Solution

Mark the Photographer Codeforces Solution

The second line of each test case contains n$n$ integers a1$a_1$, a2$a_2$, ..., an$a_n$ (0≤ai≤109$0\le a_i\le {10}^9$) — the dust level of each room.

It is guaranteed that the sum of n$n$ across all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

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.