Given an array A of positive integers, A[i] represents the value of the i-th sightseeing spot, and two sightseeing spots i and j have distance j - i between them.
The score of a pair (i < j) of sightseeing spots is (A[i] + A[j] + i - j) : the sum of the values of the sightseeing spots, minus the distance between them.
Return the maximum score of a pair of sightseeing spots.
 
Example 1:
Input: [8,1,5,2,6]
Output: 11
Explanation: i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11

 
Note:

2 <= A.length <= 50000
1 <= A[i] <= 1000

Difficulty: interview

Starter code:

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        

Solutions:
class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        curmaxsight = A[0] - 1
        curmaxpair = 0
        for sight in A[1:]:
            if sight + curmaxsight > curmaxpair:
                curmaxpair = sight + curmaxsight
            if sight > curmaxsight:
                curmaxsight = sight
            curmaxsight -= 1
        return curmaxpair
            


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        result = 0
        current = A[0]
        current_pos = 0
        for i in range(1, len(A)):
            value = current + A[i] + current_pos - i
            if value > result:
                result = value
            if current <= A[i] + i-current_pos:
                current = A[i]
                current_pos = i

        return result


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        res = 0
        m = A[0]
        
        for j in range(1, len(A)):
            res = max(res, A[j] - j + m)
            m = max(m, A[j] + j)
        
        return res


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        ans = -math.inf
        best = -math.inf
        for i,a in enumerate(A):
            ans = max(ans, best + a - i)
            best = max(best, a + i)
        
        return ans

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        i = 0
        ans = float('-inf')
        
        for j in range(1,len(A)):
            ans = max(ans, A[i] + A[j] + i - j)
            
            if A[j] + j >= A[i] + i:
                i = j
        return ans

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        i = 0
        max_degree = A[i] + i
        max_score = -float('inf')
        
        for j in range(1, len(A)):
            curr_max_score = A[j] - j + max_degree
            max_score = max(max_score, curr_max_score)
            max_degree = max(max_degree, A[j]+j)
            
        return max_score

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        
        ans = float('-inf')
        if len(A)<2: return 0
        one = A[0]
 
        for i in range(1,len(A)):
            ans = max(ans,one+A[i]-i)
            one = max(one, A[i]+i)
        
        return ans

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        # consider B[i] = A[i] + i, C[i] = A[i] -j
        # Find the B[i] + C[j]
        B = [A[i] + i for i in range(len(A))]
        C = [A[i] - i for i in range(len(A))]
        p = 0 
        q = 1
        max_score = float('-inf')
        # for each q = 1, 2,..., len(A) - 1
        # update the max of B[0], ...., B[j-1]: B[p]
        # calculate B[q] - B[p]
        while q < len(B):
            if B[q-1] > B[p]:
                p = q - 1 
            max_score = max(max_score, B[p] + C[q])
            q += 1
        return max_score
            
            
        
        


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        sA = sorted(enumerate(A), key= lambda x:x[1], reverse=True)
        # print(sA)

        L = len(A)
        maxScore = -L   #invalid value, just for initialization
        theDis = -1  #invalid value, just for initialization, minimal dis should be 1
        for i in range(L-1):
            if sA[i][1] + sA[i+1][1] <= maxScore + 1:
                # print('too small to continue', i)
                break  #two small to continue
            for j in range(i+1, L):
                curScore = sA[i][1] + sA[j][1]
                if curScore <= maxScore + 1:
                    # print('internal break', i, j)
                    break
                curDis = abs(sA[i][0]-sA[j][0])
                curScore -= curDis
                if curScore > maxScore:
                    maxScore = curScore
                    theDis = curDis 
        return maxScore


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        res = imax = 0
        for i, a in enumerate(A):
            res = max(res, imax + A[i] - i)
            imax = max(imax, A[i] + i)
        return res

#     int n = a.size();
#     int maxOverallGain = INT_MIN;
#     int maxEndRight = a[n-1] - (n-1);
#     for(int i=n-2; i>=0; i--)
#     {
#         maxEndRight = max(maxEndRight, a[i+1] - (i+1));
#         maxOverallGain = max(maxOverallGain, a[i] + i + maxEndRight);
#     }
#     return maxOverallGain;


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        maxI = A[0]
        ans = A[0] + A[1] - 1
        for i in range(1, len(A)):
            if ans < maxI + A[i] - i:
                ans = maxI + A[i] - i
            if maxI < A[i] + i:
                maxI = A[i] + i
        return ans

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        i_sum = []
        j_sum = []
        prev = -float('inf')
        max_sum = -float('inf')
        for i in reversed(list(range(len(A)))):
            if i > 0:
                if A[i]-i > prev:
                    j_sum.append(A[i]-i)
                    prev = A[i] - i
                else:
                    j_sum.append(prev)
            i_sum.append(A[i]+i)
        for i in reversed(list(range(1,len(i_sum)))):
            max_sum = max(max_sum, i_sum[i]+j_sum[i-1])
        return max_sum



class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        res = maxx = 0
        for i in range(len(A)):
            res = max(res, maxx+A[i])
            maxx = max(maxx, A[i]) - 1
        return res

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        # score = A[i] + A[j] + i - j = A[i] + i + A[j] - j
        # max(A[i]+i + A[j] - j) = max(A[i]+i) + max(A[j]-j), i<j
        max_i = 0
        score_max_i_j = []
        for j in range(len(A)):
            score_max_i_j.append(max_i + A[j] - j)
            max_i = max(max_i, A[j]+j)
        return max(score_max_i_j)





class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        a, b, n = 0, 1, len(A)
        def opt(i,j):
            return A[i] + A[j] + i - j
        
        ans = [A[0], opt(0,1)] + [0 for _ in range(n-2)]
        
        for i in range(2, n):
            opt_a, opt_b = opt(a, i), opt(b, i)
            if opt_a > opt_b:
                ans[i] = opt_a
                b = i
            else:
                ans[i] = opt_b
                a = b
                b = i
        
        return max(ans)


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        res = 0
        n = len(A)
        m = A[0]
        j = 0
        for i in range(1, n):
            res = max(res, (A[i]+A[j]+j-i))
            if A[i]+i-j > m:
                m = A[i]
                j = i
        return res

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        # consider B[i] = A[i] + i, C[i] = A[i] -j
        # Find the B[i] + C[j]
        B = [A[i] + i for i in range(len(A))]
        C = [A[i] - i for i in range(len(A))]
        p = 0 
        q = 1
        max_score = 0 
        # for each q = 1, 2,..., len(A) - 1
        # update the max of B[0], ...., B[j-1]: B[p]
        # calculate B[q] - B[p]
        while q < len(B):
            if B[q-1] > B[p]:
                p = q - 1 
            max_score = max(max_score, B[p] + C[q])
            q += 1
        return max_score
            
            
        
        


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        # A = [8 , 1 ,5 ,2 6,]
        # output = 11
        # Explanation:
            # i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11
            
        # print(A)
        
#         max_score = 0
        
#         for i in range(len(A)):
#             first = A[i] # this is my number
#             for j in range(0,len(A)):
#                 second = A[j]
#                 max_score = max(max_score ,A[i] + A[j] + i - j )      
#                 print(A[i] + A[j])
#             return max_score
        
        i = A[0]
        max_ans = 0
        for j in range(1,len(A)):
            x = A[j]
            print(x)
            max_ans = max(max_ans, i + x - j)
            i = max(i , x + j)
        return max_ans


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        # consider B[i] = A[i] + i, C[i] = A[i] -j
        # Find the B[i] + C[j]
        B = [A[i] + i for i in range(len(A))]
        C = [A[i] - i for i in range(len(A))]
        p = 0 
        q = 1
        max_score = 0 

        while q < len(B):
            if B[q-1] > B[p]:
                p = q - 1 
            max_score = max(max_score, B[p] + C[q])
            q += 1
        return max_score
            
            
        
        


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        preMax = A[0]
        ans = 0
        for i, a in enumerate(A[1:], 1):
            ans = max(ans, a - i + preMax)
            preMax = max(preMax, a + i)
            # print(preMax,ans)
        return ans

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        res = imax = 0
        for i, a in enumerate(A):
            res = max(res, imax + A[i] - i)
            imax = max(imax, A[i] + i)
        return res

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        best_of_prev = A[0] - 1
        maximum = 0
        
        for spot in A[1:]:
            if spot + best_of_prev > maximum:
                maximum = spot + best_of_prev
                
            if spot > best_of_prev:
                best_of_prev = spot
                
            best_of_prev -= 1
            
        return maximum


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        res = 0
        maximum = A[0]
        for i in range(1, len(A)):
            cur = A[i]-i
            res = max(res, cur+maximum)
            maximum = max(maximum, A[i]+i)
            
        return res

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        ans = 0
        best_pre = 0
        for i in range(1,len(A)):
            ans = max(ans, A[best_pre]+best_pre + A[i]- i)
            if A[i]+i >  A[best_pre] + best_pre:
                best_pre = i
        return ans


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        # A = [8 , 1 ,5 ,2 6,]
        # output = 11
        # Explanation:
            # i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11
        i = A[0]
        max_ans = 0
        for j in range(1,len(A)):
            x = A[j]
            print(x)
            max_ans = max(max_ans, i + x - j)
            i = max(i , x + j)
        return max_ans



class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        best = 0
        i = 0
        for j in range(1, len(A)):
            s1 = A[i] + A[j] + i - j
            s2 = A[j] + A[j-1] + j - 1 - j
            if s2 > s1:
                i = j - 1
            best = max(best, s1, s2) 
        return best


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        lmax=A[0]
        gmax=float('-inf')
        for i in range(1,len(A)):
            cur=lmax+A[i]-i
            lmax=max(lmax,A[i]+i)
            gmax=max(gmax,cur)
            
        return gmax

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:  # O(n log n)?
        # dynamic programming / memoization solution?  => wrong!!!
        ## [1, 2, 3, 4] => [[1, 2], [2, 3], [3, 4]]  sum: a + b - 1
        ##                             [[1, 3], [2, 4]] sum: [a, b-1] + [b] - 1  # get midpoint and look-up left and right parts
        ##                                  [[1, 4]] sum: [1:2] + [3:4] -1
        
        ### example: A = [8,1,5,2,6]
        ## memo[dist=1]: [8+1-1=8, 1+5-1=5, 5+2-1=6, 2+6-1=7]
        ## memp[dist=2]: [8+5-1=13]
        # memo = {(i, i): A[i] for i in range(A)}  # (i, j) = sum(i:j)
        # max_score = 0  # max(memo.values())
        # for dist in range(1, len(A)):
        #     for i in range(len(A) - dist):
        #         # get sum
        #         mid = (i + dist) // 2  # for pairs of dist 1 => 0, 1; mid == 0
        #         left_sum = memo[(i, mid)]
        #         right_sum = memo[(mid+1, i+dist)]
        #         memo[(i, i + dist)] = left_sum + right_sum - 1
        #         max_score = max(memo[(i, i + dist)], max_score)  # update max score
        # return max_score
        
        ## idea 2: lagging and leading pointers => calc their score. Move leading on, if score goes down, move lagging next
        lag, lead = 0, 1
        prev_max_score = A[0]
        prev_max_idx = 0
        max_score = 0
        for i in range(1, len(A)):
            score = prev_max_score + A[i] - (i - prev_max_idx)
            max_score = max(score, max_score)
            if A[i] >= score - A[i]:
                prev_max_idx = i
                prev_max_score = A[i]
            
        return max_score

# ex: [100, 1, 1, 1, 1....[1]*_99_, 51, 51, 1, 1, [1]*_99_, 100]


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        best_i = 0 
        res = 0
        for i, v in enumerate(A):
            res = max(res, v-i+best_i)
            best_i = max(best_i, v+i)
        return res

        return res
        # best_i = 0
        # res = 0 
        # for i, v in enumerate(A):
        #     res = max(res, v-i+best_i)
        #     best_i = max(best_i, v+i)
        # return res
        # best_i = 0
        # res = 0 
        # for i, v in enumerate(A):
        #     res = max(res, v- i + best_i)
        #     best_i = max(best_i, v+i)
        # return res


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        d=0
        m=A[0]
        for i in range(1,len(A)):
            d=max(d,A[i-1]+(i-1))
            m=max(A[i]-i+d,m)
        return m


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        best_of_prev = A[0] - 1
        maximum = 0
        
        for spot in A[1:]:
            if spot + best_of_prev > maximum:
                maximum = spot + best_of_prev
                
            if spot > best_of_prev:
                best_of_prev = spot
                
            best_of_prev -= 1
            
        return maximum


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        n = len(A)
        pre = A[0] + 0
        res = 0
        for i in range(1, n):
            # res = max(res, pre + A[i] - i)
            # pre = max(pre, A[i] + i)
            res = res if res > pre + A[i] - i else pre + A[i] - i
            pre = pre if pre > A[i] + i else A[i] + i
        return res


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        n = len(A)
        res = max_i = -n
        for j in range(1,n):
            max_i = max(max_i, A[j-1] + j-1)
            res = max(res, max_i + A[j] - j)
        return res
        


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        idx = [0]
        for i in range(1, len(A)):
            if A[i]+i-idx[-1]> A[idx[-1]]:
                idx.append(i)
        res = float('-inf')
        i = 1 
        j = 0
        #print(idx)
        while i < len(A):
            if j+1 < len(idx) and idx[j+1] < i:
                j += 1            
            res = max(res, A[i]+A[idx[j]]+idx[j]-i)
            i += 1
        return res
            


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        
        arr = [A[0] + A[j] - j for j in range(1, len(A))]
        print(arr)
        maxdiff = 0
        ans = max(arr)
        for j in range(1, len(arr)):
            maxdiff = max(maxdiff, A[j] - A[0] + j)
            ans = max(ans, arr[j] + maxdiff)
        return ans

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        max_score = 0
        
        # prev = ans = -float('inf')
        # for i in range(1, len(A)):
        #     prev = max(prev, A[i-1]+i-1)
        #     ans = max(ans, prev+A[i]-i)
        # return ans
        prev = ans = -float('inf')
        # A[i] + A[j] + i - j
        for i in range(1, len(A)):
            prev = max(prev, A[i-1] + i - 1)
            ans = max(ans, prev + A[i]-i)
        return ans


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        
        
        i_sum = [0]*len(A)
        
        j_sum = [0]*len(A)
        
        for i in range(len(A)):
            i_sum[i] = A[i] + i
        
        i_sum[-1] = 0
        for j in range(len(A)):
            j_sum[j] = A[j] - j
            
        print(j_sum)
        prefix_sum = [-float('inf')]*len(A)
        for j in  range(len(A)-2,-1,-1):
            prefix_sum[j] = max(j_sum[j+1], prefix_sum[j+1])
            
        max_sum = -float('inf')
        for i in range(len(A)):
            max_sum = max(max_sum,prefix_sum[i] + i_sum[i])
        print(prefix_sum)
        return max_sum
        


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        
        n = len(A)
        # dp = [0] * n
        # dp[0] = A[0]
        dp = 0
        ans = 0
        for j in range(0,n):
            # ans = A[j]-j + max_i{0, j-1}(A[i]+i)
            #     = A[j]-j] + dp[j-1]
            # dp[j] = max(dp[j-1], A[j]+j)
            # ans = max(ans, A[j]-j + dp[j-1])
            # dp[j] = max(dp[j-1], A[j]+j)
            ans = max(ans, A[j]-j + dp)
            dp = max(dp, A[j]+j)
        # print(dp)
        return ans

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
#         maxScore = 0 

#         for i in range(0,len(A)):
#             for j in range(i+1,len(A)):
#                 val = A[i] + A[j] + i - j 
#                 if val > maxScore:
#                     maxScore = val 
#         return maxScore
        best = 0
        i = 0
        for j in range(1, len(A)):
            s1 = A[i] + A[j] + i - j
            s2 = A[j] + A[j-1] - 1 
            if s2 > s1:
                i = j - 1
            best = max(best, s1, s2) 
        return best

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        cur, ans = 0, 0
        for a in  A:
            ans = max(ans, cur + a)
            cur = max(cur, a) -1
        return ans


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        #we want to find the two biggest numbers closest to eachother.
        dp_i = [0 for i in range(len(A))]
        dp_j = [0 for i in range(len(A))]
        dp_i[0] = A[0]
        dp_j[-1] = A[-1] - (len(A) - 1)
        for i in range(1, len(A)):
            dp_i[i] = max(A[i] + i, dp_i[i - 1])
        for j in range(len(A) - 2, -1 , -1):
            dp_j[j] = max(A[j] - j, dp_j[j + 1])
        max_sum = 0

        for i in range(len(A) - 1):
            max_sum = max(max_sum, dp_i[i] + dp_j[i + 1])
    
        return max_sum
            


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        total = 0
        n = len(A)
        if n <= 2:
            return sum(A) - 1
        
        a_1 = [a+i for i, a in enumerate(A)]        
        a_2 = [a-j for j, a in enumerate(A)]
        
        dp2 = [a for a in a_2]
        for i in range(n-2, -1, -1):
            dp2[i] = max(dp2[i+1], a_2[i+1])
           
        dp1 = [a for a in a_1]
        dp1[0] += dp2[0] 
        for i in range(1, n-1):
            dp1[i] = max(a_1[i]+dp2[i], dp1[i-1])
        
        return dp1[-2]


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        point = (A[0], 0)
        best_val = A[0]
        best_ind = 0
        max_score = 0
        for ind in range(1, len(A)):
            max_score = max(max_score, best_val+A[ind]+best_ind-ind)
            if A[ind]+ind-best_ind >= best_val:
                best_val = A[ind]
                best_ind = ind
        return max_score

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        d = A[1]+A[0]-1
        m = A[0]
        for j in range(1, len(A)):
            if m+ A[j] - j > d:
                d = m+A[j]-j
            if A[j]+j >= m:
                m = A[j]+j
        return d

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        if len(A) <= 1:
            return 0
        max_A_plus_i = max(A[0], A[1]+1)
        max_score = A[0] + A[1] - 1
        for i in range(2, len(A)):
            max_score = max(max_score, max_A_plus_i + A[i] - i)
            max_A_plus_i = max(max_A_plus_i, A[i] + i)
            
            
            
        return max_score

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        res = 0
        keep = (A[0], 0)
        for j in range(1, len(A)):
            res = max(res, keep[0] + A[j] + keep[1] - j)
            if A[j] >= keep[0] or keep[0] - A[j] < j - keep[1]:
                keep = (A[j], j)
            # print(j, keep, res)
        return res

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        cur=res=0
        for i,a in enumerate(A):
            print(res, cur)
            res = max(res,  cur + a - i)
            cur = max(cur, a + i)
        return res

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        st = []
        ret = 0
        for i, s in enumerate(A):
            while len(st) > 0 and  st[-1][0] < s:
                s_j, j = st.pop()
                ret = max(ret, s+s_j-abs(i-j))
            if len(st) > 0:
                ret = max(ret, s+st[-1][0]-abs(st[-1][1]-i))
            
            st.append((s, i))
        return ret

#
# @lc app=leetcode id=1014 lang=python3
#
# [1014] Best Sightseeing Pair
#
# https://leetcode.com/problems/best-sightseeing-pair/description/
#
# algorithms
# Medium (50.18%)
# Likes:    266
# Dislikes: 15
# Total Accepted:    10.6K
# Total Submissions: 21K
# Testcase Example:  '[8,1,5,2,6]'
#
# Given an array A of positive integers, A[i] represents the value of the i-th
# sightseeing spot, and two sightseeing spots i and j have distance j - i
# between them.
# 
# The score of a pair (i < j) of sightseeing spots is (A[i] + A[j] + i - j) :
# the sum of the values of the sightseeing spots, minus the distance between
# them.
# 
# Return the maximum score of a pair of sightseeing spots.
# 
# 
# 
# Example 1:
# 
# 
# Input: [8,1,5,2,6]
# Output: 11
# Explanation: i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11
# 
# 
# 
# 
# Note:
# 
# 
# 2 <= A.length <= 50000
# 1 <= A[i] <= 1000
# 
#
class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        # Count the current best score in all previous sightseeing spot.
        # Note that, as we go further, the score of previous spot decrement.
        cur = res = 0
        for a in A:
            res = max(res, cur + a)
            cur = max(cur, a) - 1
        return res
        



class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        maxa = [x+i for i, x in enumerate(A)]
        for i in range(1, len(maxa)): maxa[i] = max(maxa[i], maxa[i-1])
        
        res = float('-inf')
        for j in range(1, len(A)):
            res = max(res, A[j] - j + maxa[j-1])
        
        return res


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        m = -float('inf')
        res = -float('inf')
        for i in range(len(A)-1,-1,-1):
            res = max(res,A[i]+i+m)
            m = max(m,A[i]-i)
        return res


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        N = len(A)
        max_ = 0
        prev = A[-1]-N+1
        for i in range(N-2,-1,-1):
            max_ = max(max_, prev + A[i]+i)
            prev = max(prev, A[i]-i)
        return max_

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        res = float('-inf')
        maxleft = float('-inf')
        for i, a in enumerate(A):
            res = max(res, maxleft + a - i)
            maxleft = max(maxleft, a + i)
        return res

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        
        # generate a vector
        #A_left = [a + i for i, a in enumerate(A)]
        #A_right = [a - i for i, a in enumerate(A)]
        _max_left = A[0]
        _max = 0
        for j in range(1, len(A)):
            _max = max(_max_left + A[j] - j, _max)
            _max_left = max(_max_left, A[j] + j)
        return _max

class Solution:
    def maxScoreSightseeingPair(self, a: List[int]) -> int:
        d=[]
        
        for i in range(len(a)-1,-1,-1):
            if i!=0:
                d.append([a[i]-i,i])
        d.sort()
        s=0
        for i in range(0,len(a)-1):
            while d[-1][1]<=i:
                d.pop()
        
            s=max(s,a[i]+i+d[-1][0])
        return s
            
            
        
            
        
        
        
        
            


class Solution:
    def maxScoreSightseeingPair(self, a: List[int]) -> int:
        d=[]
        
        for i in range(len(a)-1,-1,-1):
            if i!=0:
                d.append([a[i]-i,i])
        d.sort()
        s=0
        for i in range(0,len(a)):
            while d!=[] and d[-1][1]<=i:
                d.pop()
            if d==[]:
                break
            s=max(s,a[i]+i+d[-1][0])
        return s
            
            
        
            
        
        
        
        
            


import heapq
import math

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        h = []
        ans = -math.inf
        
        for i,a in enumerate(A):
            if h:
                ans = max(ans, a-i-h[0])
            heapq.heappush(h, -i-a)
        return ans


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        prev=ans=float('-inf')
        for i in range(1,len(A)):
            prev=max(prev,A[i-1]+i-1)
            ans=max(ans,prev+A[i]-i)
        return ans

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        
        # generate a vector
        A_left = [a + i for i, a in enumerate(A)]
        A_right = [a - i for i, a in enumerate(A)]
        _max_left = A_left[0]
        _max = 0
        for j in range(1, len(A_right)):
            _max = max(_max_left + A_right[j], _max)
            _max_left = max(_max_left, A_left[j])
        return _max

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        left = 0
        res = 0
        max_pre = 0
        curr_res = 0
        for right in range(1, len(A)):
            max_pre = max(max_pre, A[right-1] + (right-1))
            curr_res = max_pre + A[right] - right
            res = max(res, curr_res)
        return res

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        res, leftmax, cnt = 0, 0, 0
        for num in A:
            res = max(res, num + leftmax - cnt)
            if num > leftmax - cnt:
                leftmax = num
                cnt = 0
            cnt += 1
        return res

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        ans = 0
        best = A[0]-1
        for i in range(1, len(A)):
            ans = max(ans, A[i]+best)
            best = max(best-1, A[i]-1)
        return ans

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        best = 0
        i = 0
        for j in range(1, len(A)):
            s1 = A[i] + A[j] + i - j
            s2 = A[j] + A[j-1] + j - 1 - j
            if s2 > s1:
                i = j - 1
            best = max(best, s1, s2) 
        return best            

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
#         maxScore = 0 

#         for i in range(0,len(A)):
#             for j in range(i+1,len(A)):
#                 val = A[i] + A[j] + i - j 
#                 if val > maxScore:
#                     maxScore = val 
#         return maxScore

        K    = A[0]
        best = float('-inf')
        for j in range(1,len(A)):
            x    = A[j]
            best = max(best, K + x - j )
            K    = max(K   , x + j     )
        return best

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        max_score = 0
        scores = [0] *len(A)
        for i in range (1,len(A)):
            if i == 1:
                scores[i] = A[0] - (len(A) - (i - 1))
            else:
                scores[i] = max(A[i - 1] - (len(A) - (i - 1)),scores[i-1])
        
        for j in range (1,len(A)):
            adj_score = (len(A) - j) + scores[j] + A[j]
            if adj_score > max_score:
                max_score = adj_score
        return max_score
            


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        m = p = 0
        for i, n in enumerate(A):
            m = max(m, p + n - i)
            p = max(p, n + i)
        return m

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        left = [i+a for i,a in enumerate(A)]
        right = [b-j for j, b in enumerate(A)]
        for i in range(1, len(left)):
            left[i] = max(left[i], left[i-1])
        for i in range(len(right)-1)[::-1]:
            right[i] = max(right[i], right[i+1])
        return max(l+r for l, r in zip(left[:-1], right[1:]))


import heapq
class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        return solution(A)

        
def solution(A):
    right_heap = [(-(a - i), a, i) for i, a in enumerate(A)]
    
    heapq.heapify(right_heap)
    current_max = -1    
    
    for i in range(len(A) - 1):
        right_max_score = -1
        while len(right_heap) > 0 and right_heap[0][2] <= i:
            heapq.heappop(right_heap)
        el = right_heap[0]

        right_max_score = A[i] + el[1] - abs(el[2] - i)
        current_max = max(right_max_score, current_max)

    return current_max

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        cur = res = 0
        for a in A:
            res = max(res, cur + a)
            cur = max(cur, a) - 1
        return res
    


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        return self.with_sort(A)
    
    def with_sort(self, A):
        n = len(A)
        max_list = [(i[0] + i[1], i[0]) for i in sorted(enumerate(A), 
                                                        key=lambda x:-(x[1] + x[0] * 1.000000001))]
        idx = 0
        max_s = 0
        for j in range(n-1, -1, -1):
            s = A[j] - j
            while idx < n and max_list[idx][1] >= j:
                idx += 1
            if idx < n:
                s += max_list[idx][0]
            max_s = max(max_s, s)
        return max_s
        
        
        
    def count_sort(self, A):
        C = [[] for _ in range(51001)]
        for i, a in enumerate(A):
            C[a + i].append((a+i, i))
        res = []
        k = 0
        for c in C:
            if len(c) > 0:
                res.extend(c)
        return list(reversed(res))
        
        
    def brute_force(self, A):
        max_score = 0
        n = len(A)
        for i in range(n):
            for j in range(i+1, n):
                s = A[i] + A[j] + i - j
                if s > max_score:
                    max_score = s
        return max_score


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        if len(A) < 2:
            return -1
        
        best_so_far = A[0] + 0
        res = 0
        for j in range(1, len(A)):
            res = max(res, best_so_far + A[j] - j)
            if best_so_far < A[j] + j:
                best_so_far = A[j] + j
        
        return res

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        res = imax = 0
        for i, a in enumerate(A):
            res = max(res, imax + a - i)
            imax = max(imax, a + i)
        return res

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        if len(A) <= 1:
            return -float('inf')

        candidate = max(A[0], A[1]+1)
        res = A[0]+A[1]-1 

        for i in range(2, len(A)):
            res = max(res, candidate+A[i]-i)
            candidate = max(candidate, A[i]+i)
        return res            

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        import sys
        val = A[0] + 0
        ans = -sys.maxsize
        A.pop(0)
        for i,num in enumerate(A):
            ans = max(ans,val+A[i] - i - 1)
            val = max(val,A[i]+i+1)
        return ans


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        if not A:
            return 0
        temp=A[0]
        ans=-999
        for i in range(1, len(A)):
            ans=max(ans, temp+A[i]-i)
            temp=max(temp, A[i]+i)
        return ans

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        largest = 0
        i = 0
        while(i<len(A)-1):
            largest = max(largest,A[i]+A[i+1]-1)
            if A[i]>A[i+1]:
                A[i],A[i+1]=A[i+1]+1,A[i]-1
            i += 1
        return largest
        
            


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        i = 0
        res = 0
        for j in range(1, len(A)):
            ti = A[i] + i
            res = max(A[j] - j + ti, res)
            if A[j] + j > ti:
                i = j
        return res


class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        # we have to find A[i] + i + A[j] - j
        # we will fix max(A[i] + i) and find for diff values of A[j] - j
        if len(A) == 0 : return 0
        maxI = A[0] + 0
        res = 0
        for j in range(1,len(A)):
            res = max(res,maxI+A[j]-j)
            maxI = max(maxI,A[j]+j)
        return res
        
        
        
        
        
        
        
        
        
        
        
        # for i in range(len(A)-1):
        #     for j in range(i+1,len(A)):
        #         score = max(score,A[i] + A[j] + i - j)
        # return score