You are given an integer array values, where values[i] represents the score of the sightseeing spot at index i. Choose two different indices i and j such that $i < j$, and define the score of this pair as values[i] + values[j] + i - j.

Return the maximum possible score over all valid pairs.

Constraints:

• $2 \leq$ values.length $\leq 5 \cdot 10^4$

• $1 \leq$ values[i] $\leq 1000$

Input: values = [4, 7, 3, 9, 2]-List[int]
Output: 14-int
Explanation: The best pair is i = 1, j = 3: values[1] + values[3] + 1 - 3 = 7 + 9 - 2 = 14.

Input: values = [10, 1]-List[int]
Output: 10-int
Explanation: Only one valid pair exists, i = 0, j = 1, with score 10 + 1 + 0 - 1 = 10.

Input: values = [1, 1, 1, 1, 1, 1]-List[int]
Output: 1-int
Explanation: Any pair (i, j) has score 1 + 1 + i - j = 2 - (j - i), which is maximized when j - i = 1, giving 1.

Input: values = [1000, 1, 1000, 1, 1000]-List[int]
Output: 1998-int
Explanation: The best pair is i = 0, j = 2: 1000 + 1000 + 0 - 2 = 1998 (i = 2, j = 4 also gives the same score).

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.