Stupid Machine

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/LTIME79/hindi/STUPMACH.pdf),[Bengali](http://www.codechef.com/download/translated/LTIME79/bengali/STUPMACH.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME79/mandarin/STUPMACH.pdf), [Russian](http://www.codechef.com/download/translated/LTIME79/russian/STUPMACH.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME79/vietnamese/STUPMACH.pdf) as well. As usual, I went to work in the morning. Unfortunately, I found out that my manager bought a new machine and I have to learn to operate it. There are $N$ boxes in a line (numbered $1$ through $N$). Initially, the boxes are empty, and I need to use the machine to put tokens in them. For each valid $i$, the $i$th box has a maximum capacity $S_i$ tokens. I can perform the following operation any number of times: choose an integer $L$ ($1 \le L \le N$) and put one token in each of the boxes $1, 2, \ldots, L$. My manager told me to put as many tokens as possible into the boxes in total (the distribution of tokens in the boxes does not matter). Of course, it is not allowed to perform an operation that would result in the number of tokens in some box exceeding its capacity. Can you help me calculate the maximum number of tokens that can be put in these boxes? ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains a single integer $N$.  The second line contains $N$ spaceseparated integers $S_1, S_2, \ldots, S_N$. ### Output For each test case, print a single line containing one integer  the maximum number of tokens. ### Constraints  $1 \le T \le 100$  $1 \le N \le 10^6$  $1 \le S_i \le 10^9$ for each valid $i$  the sum of $N$ over all test cases does not exceed $5 \cdot 10^6$ ### Subtasks **Subtask #1 (50 points):**  $1 \le N \le 1,000$  $1 \le S_i \le 1,000$ for each valid $i$  the sum of $N$ over all test cases does not exceed $5,000$ **Subtask #2 (50 points):** original constraints ### Example Input ``` 1 3 2 1 3 ``` ### Example Output ``` 4 ``` ### Explanation **Example case 1:** The optimal way is to perform the following operations:  Choose $L = 3$ and use the machine to put one token in each box.  Choose $L = 1$ and use the machine to put one more token in the first box.Author:  i_love_islam 
Editorial  https://discuss.codechef.com/problems/STUPMACH 
Tags  cakewalk, deadwing97, i_love_islam, ltime79 
Date Added:  26122019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 