You are tasked with planning the construction of $n$ buildings in a line, indexed from $1$ to $n$.

The heights of the buildings must satisfy the following conditions:

• The height of building $1$ must be $0$.

• The absolute difference in height between any two adjacent buildings cannot exceed $1$. That is, for every building $i$ where $1 \leq i < n$, the condition $|h_i - h_{i+1}| \leq 1$ must hold, where $h_i$ represents the height of building $i$.

• There is a $2$D array restrictions, where each restrictions[i] $= [id_i, maxHeight_i]$ specifies that building $id_i$ can have a maximum height of $maxHeight_i$.

Return the maximum possible height among all the buildings that can be constructed.

Constraints:

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

• $0 \leq$ restrictions.length $\leq \min(n - 1, 10^5)$

• $2 \leq id_i \leq$ n

• All $id_i$ are unique.

• $0 \leq maxHeight_i \leq 10^9$

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.