You want to construct an array a of length n with indices from $0$ to n $- 1$ such that:

• a[0] $= 0$

• The absolute difference between any two adjacent elements satisfies $|$ a[i + 1] $-$ a[i] $| \leq$ diff[i] for all $0 \leq i <$ n $- 1$.

• For each condition in restrictions, represented as $[idx, maxVal]$, the element at index idx satisfies a[idx] $\leq maxVal$.

Return the maximum possible value that can be achieved in the array a.

Constraints:

• $2 \leq$ n $\leq 10^5$

• $1 \leq$ restrictions.length $\leq$ n $- 1$

• restrictions[i].length $= 2$

• restrictions[i] $= [idx, maxVal]$

• $1 \leq idx <$ n

• $1 \leq maxVal \leq 10^6$

• diff.length $=$ n $- 1$

• $1 \leq$ diff[i] $\leq 10$

• The values of restrictions[i][0] are unique.

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.