Problem Description:
Humans have now set up housing societies on the moon, where the societies are very large, and each building can be very high. There are N consecutive buildings in a society. The owners decided to increase the heights of the buildings. Being aesthetically oriented, they wanted to ensure that the heights (all measured as number of floors in the building) of consecutive buildings differ at most by one floor so that the skyline of the buildings look pleasing. That is, if the heights of the buildings are h1, h2, ... hn, then after the height increase, their heights become H1, H2, .... Hn such that 1 <= Hi H(i+1) <= 1 for all i = 1, 2, ...n1. The modification is made such that the total number of floors added to the society is a minimum.
The owner of the pth building wants to know what will be the height of his building before agreeing to this plan for modification, Given the initial heights of the buildings, can you write a program to answer the query pth owner has?
Input
T number of test cases
A set of 2 lines for each of the T test cases containing
N, the number of buildings, P the position the building for which we want to know the height after modification
N space separated integers showing the original heights of the buildings
Output
T lines containing
height of the Pth building after modification for each of the T test cases
Constraints
1<=T<=50
1<=N<=104 P<=N
1<=height of each building <= 5000 (There are very tall buildings in the society)
Example 1
Input:
1
7 4
9 5 17 7 10 2 18
Output:
16
Explanation:
After modification the heights will become 15 16 17 16 16 17 18. Hence the fourth building will have height 16 floors.
Example 2
Input:
1
13 12
34 80 56 41 16 39 70 85 73 75 20 33 83
Output:
82
Explanation:
After modification, the heights would be 79 80 80 81 82 83 84 85 84 83 82 82 83
No comments:
Post a Comment