B'You are playing yet another game where you kill monsters using magic spells. There are n cells in the row, numbered from 1 to n . Initially, the i -th cell contains the i -th monster with h_i health. You have a basic spell that costs 1 MP and deals 1 damage to the monster you choose. You can cast it any number of times. Also, you have a special scroll with "Explosion" spell you can use only once. You want to finish killing monsters with explosion, that 's why you, firstly, cast the basic spell several times (possibly, zero), and then after that, you cast one "Explosion". How does "Explosion" spell work? Firstly, you choose the power of the spell: if you pour x MP into it, "Explosion" will deal x damage. Secondly, you choose some monster i , which will be targeted by the spell. That 's what happens next: Your goal is to kill all the remaining monsters with those "chaining" explosions, that 's why you need a basic spell to decrease h_i of some monsters or even kill them beforehand (monsters die when their current health h_i becomes less or equal to zero). Note that monsters don 't move between cells, so, for example, monsters i and i + 2 will never become neighbors. What is the minimum total MP you need to kill all monsters in the way you want? The total MP is counted as the sum of the number of basic spells you cast and the power x of explosion scroll you 've chosen. The first line contains one integer t ( 1 <= t <= 10^4 ) -- the number of test cases. The first line of each test case contains the single integer n ( 1 <= n <= 3 cdot 10^5 ) -- the number of cells in the row, i. e. the number of monsters. The second line of each test case contains n integers h_1, h_2, ... , h_n ( 1 <= h_i <= 10^6 ) -- the initial health of the monsters. It 's guaranteed that the sum of n over all test cases doesn 't exceed 3 cdot 10'...