Untitled

class Solution {
    public int maxValue(int n, int index, int maxSum) {
        long left = 1;
        long right = maxSum;
        int result = 0;

        while (left <= right) {
            long midVal = left + (right - left) / 2;

            long leftCount = Math.min((long) index, midVal - 1);
            long leftSum = getSumElements(leftCount, midVal);
            leftSum += Math.max(0, index - midVal + 1);

            long rightCount = Math.min((long) n - index - 1, midVal - 1);
            long rightSum = getSumElements(rightCount, midVal);
            rightSum += Math.max(0, n - index - 1 - midVal + 1);

            if (leftSum + rightSum + midVal <= maxSum) {
                result = (int) Math.max(result, midVal);
                left = midVal + 1;
            } else {
                right = midVal - 1;
            }
        }

        return result;
    }

    private long getSumElements(long count, long val) {
        return val * count - (count * (count + 1)) / 2;
    }
}