You want to build n new buildings in a city. The new buildings will be built in a line and are labeled from 1 to n.

However, there are city restrictions on the heights of the new buildings:


	The height of each building must be a non-negative integer.
	The height of the first building must be 0.
	The height difference between any two adjacent buildings cannot exceed 1.


Additionally, there are city restrictions on the maximum height of specific buildings. These restrictions are given as a 2D integer array restrictions where restrictions[i] = [idi, maxHeighti] indicates that building idi must have a height less than or equal to maxHeighti.

It is guaranteed that each building will appear at most once in restrictions, and building 1 will not be in restrictions.

Return the maximum possible height of the tallest building.

&nbsp;
Example 1:

Input: n = 5, restrictions = [[2,1],[4,1]]
Output: 2
Explanation: The green area in the image indicates the maximum allowed height for each building.
We can build the buildings with heights [0,1,2,1,2], and the tallest building has a height of 2.

Example 2:

Input: n = 6, restrictions = []
Output: 5
Explanation: The green area in the image indicates the maximum allowed height for each building.
We can build the buildings with heights [0,1,2,3,4,5], and the tallest building has a height of 5.


Example 3:

Input: n = 10, restrictions = [[5,3],[2,5],[7,4],[10,3]]
Output: 5
Explanation: The green area in the image indicates the maximum allowed height for each building.
We can build the buildings with heights [0,1,2,3,3,4,4,5,4,3], and the tallest building has a height of 5.


&nbsp;
Constraints:


	2 &lt;= n &lt;= 109
	0 &lt;= restrictions.length &lt;= min(n - 1, 105)
	2 &lt;= idi &lt;= n
	idi&nbsp;is unique.
	0 &lt;= maxHeighti &lt;= 109


class Solution:
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        arr = restrictions
        arr.extend([[1,0],[n,n-1]])
        arr.sort()
        n = len(arr)
        for i in range(1,n):
            arr[i][1] = min(arr[i][1], arr[i-1][1]+arr[i][0]-arr[i-1][0])
        for i in range(n-2,-1,-1):
            arr[i][1] = min(arr[i][1], arr[i+1][1]+arr[i+1][0]-arr[i][0])
        res = 0
        for i in range(1,n):
            #position where height can be the highest between arr[i-1][0] and arr[i][0]
            k = (arr[i][1]-arr[i-1][1]+arr[i][0]+arr[i-1][0])//2
            res = max(res, arr[i-1][1]+k-arr[i-1][0])
        return res
class Solution {
    public int maxBuilding(int n, int[][] restrictions) {
        List<int[]> list=new ArrayList<>();
        list.add(new int[]{1,0});
        for(int[] restriction:restrictions){
            list.add(restriction);
        }
        Collections.sort(list,new IDSorter());

        if(list.get(list.size()-1)[0]!=n){
            list.add(new int[]{n,n-1});
        }

       for(int i=1;i<list.size();i++){
           list.get(i)[1]=Math.min(list.get(i)[1],list.get(i-1)[1] + list.get(i)[0]-list.get(i-1)[0]);
       }

       for(int i=list.size()-2;i>=0;i--){
           list.get(i)[1]=Math.min(list.get(i)[1],list.get(i+1)[1] + list.get(i+1)[0] - list.get(i)[0]);
       }

       int result=0;
       for(int i=1;i<list.size();i++){
           int h1=list.get(i-1)[1]; // heigth of previous restriction
           int h2=list.get(i)[1]; // height of current restriction
           int x=list.get(i-1)[0]; // id of previous restriction
           int y=list.get(i)[0]; // id of current restriction

          result=Math.max(result,Math.max(h1,h2) + (y-x-Math.abs(h1-h2))/2);
       }
        return result;
    }

    public class IDSorter implements Comparator<int[]>{
        @Override
        public int compare(int[] myself,int[] other){
            return myself[0]-other[0];
        }
    }
}
class Solution {
public:
    int maxBuilding(int n, vector<vector<int>>& restrictions) {
        restrictions.push_back({1, 0});
        restrictions.push_back({n, n-1}); 
        sort(restrictions.begin(), restrictions.end()); 
        for (int i = restrictions.size()-2; i >= 0; --i) {
            restrictions[i][1] = min(restrictions[i][1], restrictions[i+1][1] + restrictions[i+1][0] - restrictions[i][0]); 
        }
        
        int ans = 0; 
        for (int i = 1; i < restrictions.size(); ++i) {
            restrictions[i][1] = min(restrictions[i][1], restrictions[i-1][1] + restrictions[i][0] - restrictions[i-1][0]); 
            ans = max(ans, (restrictions[i-1][1] + restrictions[i][0] - restrictions[i-1][0] + restrictions[i][1])/2); 
        }
        return ans; 
    }
};
/**
 * @param {number} n
 * @param {number[][]} restrictions
 * @return {number}
 */
var maxBuilding = function(n, restrictions) {
    let maxHeight=0;
    restrictions.push([1,0]);//Push extra restriction as 0 for 1
    restrictions.push([n,n-1]);//Push extra restrition as n-1 for n
    restrictions.sort(function(a,b){return a[0]-b[0]});
    //Propogate from left to right to tighten the restriction: Check building restriction can be furhter tightened due to the left side building restriction.
    for(let i=1;i<restrictions.length;i++){
        restrictions[i][1] = Math.min(restrictions[i][1], (restrictions[i][0]-restrictions[i-1][0])+restrictions[i-1][1]);
    }
    //Propogate from right to left to tighten the restriction: Check building restriction can be furhter tightened due to the right side building restriction.
    for(let i=restrictions.length-2;i>=0;i--){
        restrictions[i][1] = Math.min(restrictions[i][1], (restrictions[i+1][0]-restrictions[i][0])+restrictions[i+1][1]);
    }
    let max=0;
    for(let i=0;i<restrictions.length-1;i++){
        let leftHeight = restrictions[i][1];
        let rightHeight = restrictions[i+1][1];
        let distance = restrictions[i+1][0]-restrictions[i][0]-1;//Number of cities between ith and i+1th city, excluding these cities
        let hightDiff = Math.abs(restrictions[i+1][1]-restrictions[i][1]);
        let middleHeight = Math.max(leftHeight,rightHeight)+Math.ceil((distance-hightDiff)/2);
        max = Math.max(max,middleHeight);
    }
    return max;
};
Maximum Building Height