# Pikachu and Stones solution codechef

## Pikachu and Stones solution codechef

Charizard and Dragonite have a Pokemon tournament scheduled today. In order to keep Pikachu busy they gave him a task. He is given NN piles of stones with where ithith pile has AiAi stones, and his task is to make a peak from the piles of stones without moving stones from one pile to another.

Collection of piles make a peak if the no of stones in the pile is strictly increasing from index 11 to ii and then strictly decreasing from index ii to nn where 2in12≤i≤n−1.

Pikachu wants to watch the tournament so he asked for your help to complete the task. Your task is to calculate the minimum number of additional stones required to make a peak from the piles of stones.

### Input: Pikachu and Stones solution codechef

• First line will contain TT, number of testcases. Then the testcases follow.
• Each testcase contains a single integer NN.
• Next line contains NN space separated integers.

### Output: Pikachu and Stones solution codechef

For each testcase, output in a single integer that is the minimum number of stones required.

### Constraints Pikachu and Stones solution codechef

• 1T1001≤T≤100
• 3N1053≤N≤105
• 0Ai1090≤Ai≤109
• Sum of NN over all test cases doesn’t exceed 105105

### Sample Input: Pikachu and Stones solution codechef

2


7
1 5 2 4 2 8 5
8
3 2 4 6 7 2 8 4

### Sample Output: Pikachu and Stones solution codechef

14


10