509. Maximum Value at a Given Index in a Bounded Array

Construct an array of n positive integers where every element is at least 1, the absolute difference between adjacent elements is at most 1, the total sum does not exceed maxSum, and arr[index] is maximized. Return the maximum possible value of arr[index]. Input: 'n, index, maxSum'.

Input: 'n, index, maxSum'.

Output: Integer — the maximum value at the index.

Examples

Input: 4, 2, 6
Output: 2
Explanation: e.g. [1,2,2,1] sums to 6.

Input: 6, 1, 10
Output: 3
Explanation: Peak at index 1.

Input: 1, 0, 5
Output: 5
Explanation: Single element takes the whole sum.

Constraints

• 1<=n<=10^9
• 0<=index<n
• n<=maxSum<=10^9

Asked by