## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Pushpa CodeChef Solution | CodeChef Problem Solution 2022

Pushpa has entered Chefland and wants to establish Pushpa-Raj here too.

Chefland consists of $N$ floating wooden logs. Each log has a positive integer written on it which denotes the height of the log from ground. The ${i}^{th}$ wooden log is initially floating at a height ${H}_{i}$ from the ground.

Pushpa will initially start by jumping on any wooden log of his choice. He has the power to jump any horizontal distance, but he can jump from a wooden log at height $X$ to a wooden log at height $\left(X+1\right)$ only.

Moreover, in Chefland, gravitational pull is affected by the jumps made and as a result when Pushpa jumps on a wooden log $A$, then the wooden log $A$ first sinks by $1$ unit and then all the wooden logs rise by $1$ unit. More formally, wooden log $A$ maintain its height whereas rest logs rise by $1$ unit.

To establish his rule, Pushpa wants to achieve the maximum height possible. Determine the maximum height he will achieve from the ground.

### Input Format

• The first line contains a single integer $T$ - the number of test cases. Then the test cases follow.

• The first line of each test case contains an integer $N$ - the number of wooden logs.
• The second line of each test case contains $N$ space-separated integers ${H}_{1},{H}_{2},\dots ,{H}_{N}$ denoting the initial heights of the logs from the ground.

### Output Format

For each testcase, output in a single line the maximum height achieved by Pushpa.

### Constraints

• $1\le T\le 10$
• $1\le N\le {10}^{5}$
• $1\le {H}_{i}\le {10}^{9}$

### Sample Input 1

2
4
1 2 1 3
1
2


### Sample Output 1

3
2


### Explanation

• Test case $1$: If Pushpa chooses to start from wooden log at index $1$ with height of $1$ units, then the new heights will be $\left[1,3,2,4\right]$. He can then jump to log at height $2$ units after which he is unable to make any jumps. To achieve the maximum height, he chooses wooden log at height $3$ and achieves a height of $3$ units.
• Test case $2$: There is only $1$ wooden log so Pushpa reaches the height of $2$ units.