#include <vector>
#include <array>
#include <algorithm>
using namespace std;

// 演算法同 C 版 / Same algorithm as the C version:
// 加入 [1,0] 與 [n,∞] → 排序 → 左右兩掃收緊上界 → 相鄰對取峰值最大。
// Add [1,0] and [n,∞] → sort → two passes tighten bounds → max peak over adjacent pairs.

class Solution {
public:
    int maxBuilding(int n, vector<vector<int>>& restrictions) {
        // vector<array<long,2>>：每個元素是 {id, height}，用 long 防止溢位。
        // vector<array<long,2>>: each element is {id, height}; long avoids overflow.
        vector<array<long, 2>> r;
        r.reserve(restrictions.size() + 2);       // 預留空間，避免多次擴容 / reserve to avoid reallocs

        r.push_back({1, 0});                       // 第 1 棟固定為 0 / building 1 fixed at 0

        bool hasN = false;                         // n 是否已被約束 / is building n restricted?
        for (auto& res : restrictions) {           // range-for：逐一取出每條約束 / iterate each restriction
            r.push_back({res[0], res[1]});         // res[0]=id, res[1]=maxHeight
            if (res[0] == n) hasN = true;          // 記錄是否含最後一棟 / note building n
        }
        // 最後一棟若無約束，加上「近乎無限」上限讓掃描算出真正高度。
        // If n unrestricted, add a near-infinite cap so passes derive its true height.
        if (!hasN) r.push_back({(long)n, 2000000000L});

        // 用 lambda 依 id 排序；[](){} 是匿名函式，當作比較器傳給 sort。
        // Sort by id using a lambda; [](){} is an anonymous function used as comparator.
        sort(r.begin(), r.end(),
             [](const array<long,2>& a, const array<long,2>& b){ return a[0] < b[0]; });

        int m = r.size();                          // 約束總數 / total number of restrictions

        // 左掃：高度不能超過 左鄰 + 距離（每步最多差 1）。
        // Left pass: cap by left neighbor's height plus distance.
        for (int i = 1; i < m; i++)
            r[i][1] = min(r[i][1], r[i-1][1] + (r[i][0] - r[i-1][0]));

        // 右掃：同理從右鄰收緊。
        // Right pass: tighten from the right neighbor.
        for (int i = m - 2; i >= 0; i--)
            r[i][1] = min(r[i][1], r[i+1][1] + (r[i+1][0] - r[i][0]));

        // 相鄰對的峰值公式 (hl+hr+d)/2，取最大。
        // Peak (hl+hr+d)/2 for each adjacent pair; take the maximum.
        long best = 0;
        for (int i = 0; i + 1 < m; i++) {
            long d = r[i+1][0] - r[i][0];          // 兩棟距離 / distance
            best = max(best, (r[i][1] + r[i+1][1] + d) / 2); // 更新最大峰值 / update max peak
        }
        return (int)best;                          // 回傳結果 / return answer
    }
};