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: 2017-01-11 03:53:46

I'm sorry it seems the testcase is broken (dont know why for sure), all submission will be rejudged :)

fwildanf: 2017-01-11 01:41:21

._.

Andy: 2017-01-10 15:52:47

teman2 2016, salahkan arianto ya wkwk

farrasr: 2017-01-10 14:36:16

...

chrele: 2017-01-10 14:33:09

:')


Added by:Andy
Date:2014-10-21
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:NPC Schematics 2014