Pushpa solution codechef

Pushpa solution codechef

 

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

Chefland consists of NN floating wooden logs. Each log has a positive integer written on it which denotes the height of the log from ground. The ithith wooden log is initially floating at a height HiHi 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 XX to a wooden log at height (X+1)(X+1) only.

Moreover, in Chefland, gravitational pull is affected by the jumps made and as a result when Pushpa jumps on a wooden log AA, then the wooden log AA first sinks by 11 unit and then all the wooden logs rise by 11 unit. More formally, wooden log AA maintain its height whereas rest logs rise by 11 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 Pushpa solution codechef

  • 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 wooden logs.
  • The second line of each test case contains NN space-separated integers H1,H2,,HNH1,H2,…,HN 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.

Pushpa solution codechef Constraints

  • 1T101≤T≤10
  • 1N1051≤N≤105
  • 1Hi1091≤Hi≤109

Sample Input 1 

2
4
1 2 1 3
1
2

Sample Output 1 

3
2

Explanation Pushpa solution codechef

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

     Solution

    Click here

Leave a Comment

Your email address will not be published.