class Solution:
def maxValue(self, n: int, index: int, maxSum: int) -> int:
""" tc O(lg(maxSum)) sc O(1)
peak range [0,maxSum-n]
"""
n_maxSum = maxSum - n
# tc O(1)
def get_arr_sum(peak,idx,n):
res = 0
end1 = max(0,peak-idx)
res += (peak+end1)*(peak-end1+1)//2 #1
end2 = max(0,peak - ((n-1)-idx))
res += (peak+end2)*(peak-end2+1)//2 #2 #1,2 add peak twice in total
return res - peak
l, r =0,n_maxSum
while l < r :
mid = (l+r+1)//2 # mid stand for revised val at peak
if get_arr_sum(mid,index,n) > n_maxSum: # peak too big
r = mid -1
else:
l = mid
return l+ 1 # to restore offset 1 we substract at the beginning