32735번 - Card Pairs 다국어

문제

You have a hand of cards, where each card has one of $n$ types. For each $i$ from 1ドル$ to $n,ドル you have $a_i$ cards with type $i,ドル and the bank has infinite cards with type $i$.

You can perform the following trade with the bank any number of times:

Choose any two cards with the same type from your hand, and exchange them for a single card from the bank with any type except the type of the cards you just exchanged. Note that the bank only has cards with types 1ドル$ through $n,ドル so you cannot trade for cards with any other types.

For example, here is a valid sequence of trades on the first sample case:

What is the maximum number of trades you can perform?

입력

The first line of the input contains a single integer $t$ (1ドル \le t \le 10^5$) --- the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ (2ドル \le n \le 2\cdot 10^5$) --- the number of card types.

The second line of each test case contains $n$ integers $a_1, a_2 \cdots a_n$ (0ドル \le a_i \le 10^9$), where $a_i$ is the number of cards of type $i$ that you currently have.

It is guaranteed that the sum of $n$ over all test cases does not exceed 2ドル\cdot 10^5$.

출력

For each test case, print a single integer --- the maximum number of trades you can perform.

제한

힌트

The diagram above describes an optimal sequence of trades in the first test case.

In the fourth test case, it is impossible to perform any trades, since you don't start with any pair of cards with the same type, so the answer is 0ドル$.