Pushpa solution codechef
Pushpa has entered Chefland and wants to establish Pushpa-Raj here too.
Chefland consists offloating wooden logs. Each log has a positive integer written on it which denotes the height of the log from ground. The wooden log is initially floating at a height 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 heightto a wooden log at height only.
Moreover, in Chefland, gravitational pull is affected by the jumps made and as a result when Pushpa jumps on a wooden log, then the wooden log first sinks by unit and then all the wooden logs rise by unit. More formally, wooden log maintain its height whereas rest logs rise by 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 – the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer – the number of wooden logs.
- The second line of each test case contains space-separated integers denoting the initial heights of the logs from the ground.
For each testcase, output in a single line the maximum height achieved by Pushpa.
Pushpa solution codechef Constraints
Sample Input 1
2 4 1 2 1 3 1 2
Sample Output 1
Explanation Pushpa solution codechef
- Test case : If Pushpa chooses to start from wooden log at index with height of units, then the new heights will be . He can then jump to log at height units after which he is unable to make any jumps. To achieve the maximum height, he chooses wooden log at height and achieves a height of units.
- Test case
: There is only wooden log so Pushpa reaches the height of units.