# Pushpa Codechef Solution | May CHALLENGE

Share:

Pushpa Codechef Solution

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

Chefland has NN towers where the height of the ithith tower is HiHi. To establish Pushpa-Raj, Pushpa does the following:

• Initially, Pushpa chooses any tower ii (1≤i≤N)(1≤i≤N) and lands on the roof of that tower.
• Let XX denote the height of the tower Pushpa is currently on, then, Pushpa can land on the roof of any tower jj (1≤j≤N)(1≤j≤N) such that the height of the jthjth tower is (X+1)(X+1).

Let ii denote the index of the tower on which Pushpa lands, then, the height of all towers except tower ii increases by 11 after each jump including the initial jump.

To establish Pushpa-Raj, Pushpa wants to land at the maximum height possible. Determine the maximum height Pushpa can reach.

### Input Format

• The first line contains a single integer TT – the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer NN – the number of towers
• The second line of each test case contains NN space-separated integers H1,H2,…,HNH1,H2,…,HN denoting the initial heights of each of the towers from the ground.

### Output Format

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

### Constraints

• 1≤T≤101≤T≤10
• 1≤N≤1051≤N≤105
• 1≤Hi≤1091≤Hi≤109

### Sample Input 1

``````2
4
1 2 1 3
1
2
``````

### Sample Output 1

``````3
2
``````

### Explanation

• Test case 11: If Pushpa chooses to start from tower at index 11 with height of 11 unit, then, the new heights will be [1,3,2,4][1,3,2,4]. He can then jump to the 3rd3rd tower (with height 22 units). The updated heights of the towers is [2,4,2,5][2,4,2,5]. Pushpa is unable to make any more jumps.

The optimal way to in this case is to take an initial jump at tower 44 with height 33. The maximum height Pushpa can reach is 33.

• Test case 22: There is only 11 tower so Pushpa reaches the maximum height of 22 units.