## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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$ rooms. The $i$-th room has a nonnegative dust level ${a}_{i}$. He has a magical cleaning machine that can do the following three-step operation.

• Select two indices $i such that the dust levels ${a}_{i}$${a}_{i+1}$$\dots$${a}_{j-1}$ are all strictly greater than $0$.
• Set ${a}_{i}$ to ${a}_{i}-1$.
• Set ${a}_{j}$ to ${a}_{j}+1$.
Mark's goal is to make ${a}_{1}={a}_{2}=\dots ={a}_{n-1}=0$ so that he

Solution Click Below:-  👉
👇👇👇👇👇

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

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

The first line of each test case contains a single integer $n$ ($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$ integers ${a}_{1}$${a}_{2}$, ..., ${a}_{n}$ ($0\le {a}_{i}\le {10}^{9}$) — the dust level of each room.

It is guaranteed that the sum of $n$ across all test cases does not exceed $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.