NPC2014D  General Joke
A long time ago, there was a big war. This war have two sides, one is The Schematics and the other one is The Unschematicszan. Joke is a respected general of The Schematics and is feared by The Unschematicszan. On every battle, Joke and his minions always win so the elite soldiers of The Unschematicszan can't fight him.
This war goes on until one day General Joke decides to end the war. At the same time, there are still N town that are under control of The Unschematicszan, numbered from 1 to N. In each town, there are Pi elite soldiers of The Unscehmaticszan that stands guard 24 hours a day. To take over a town, General Joke must bring at least the same number of minion as the number of elite soldiers guarding that town. After taking over a town, General Joke must leave at least a minion so that town doesn't get taken back by the Unschematicszan. The winner of the fight doesn't lose any soldier/minion in the fight. After a long thought, General Joke decides to take over the town starting from town number 1 to N and asks you to count the minimum number of minions that he must bring to successfully take over all the towns.
Input
First line is T, the number of test cases. For each test case, the first line is N, the number of towns occupied by The Unschematicszan. The next line is N numbers, representing Pi which is the number of elite soldiers on town i, starting from 1 to N.
Output
Minimum number of minions that Joke must bring to win.
Sample Input
1 5 1 2 5 4 2
Sample Output
7
Constraint
 1 ≤ T ≤ 100
 1 ≤ N ≤ 100000
 1 ≤ Pi ≤ 1000000
Input file is huge, is faster I/O (scanf for C)
hide comments
Arianto Wibowo:
20170111 03:53:46
I'm sorry it seems the testcase is broken (dont know why for sure), all submission will be rejudged :) 

fwildanf:
20170111 01:41:21
._. 

Andy:
20170110 15:52:47
teman2 2016, salahkan arianto ya wkwk 

farrasr:
20170110 14:36:16
... 

chrele:
20170110 14:33:09
:') 
Added by:  Andy 
Date:  20141021 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  NPC Schematics 2014 