#include <stdlib.h>

// 演算法 / Algorithm:
// 1. 把 [1,0] 和（若需要）[n,∞] 加入約束，按 id 排序。
//    Add [1,0] and (if needed) [n,∞], then sort restrictions by id.
// 2. 左右兩次掃描，把每個約束收緊成真正的可達上界。
//    Two passes (left, right) tighten each cap to its real reachable bound.
// 3. 對每對相鄰約束用峰值公式 (hl+hr+d)/2 取最大。
//    For each adjacent pair, the peak is (hl+hr+d)/2; take the max.

// 每個約束存成一個結構：id 與高度都用 long 避免溢位。
// One restriction: id and height stored as long to avoid 32-bit overflow.
typedef struct { long id, h; } Pair;

// qsort 用的比較函式：依 id 由小到大排序。
// Comparator for qsort: order by id ascending.
static int cmp(const void *a, const void *b) {
    Pair *pa = (Pair *)a, *pb = (Pair *)b;        // 把 void* 轉回 Pair* / cast back to Pair*
    if (pa->id < pb->id) return -1;               // a 在前 / a comes first
    if (pa->id > pb->id) return 1;                // b 在前 / b comes first
    return 0;                                     // 相等（不會發生，id 唯一）/ equal (won't happen, ids unique)
}

long lmin(long a, long b) { return a < b ? a : b; } // 取兩個 long 的較小值 / min of two longs

int maxBuilding(int n, int** restrictions, int restrictionsSize, int* restrictionsColSize) {
    // 最多需要 原約束數 + 2 個位置（多出 [1,0] 與 [n,∞]）。
    // Need at most restrictionsSize + 2 slots (extra [1,0] and [n,∞]).
    Pair *r = (Pair *)malloc(sizeof(Pair) * (restrictionsSize + 2));
    int m = 0;                                    // m = 目前已放入的數量 / current count

    r[m].id = 1; r[m].h = 0; m++;                 // 第 1 棟固定為 0 / building 1 fixed at height 0

    int hasN = 0;                                 // 標記 n 是否已被約束 / does n already appear?
    for (int i = 0; i < restrictionsSize; i++) {  // 複製所有給定約束 / copy all given restrictions
        r[m].id = restrictions[i][0];             // restrictions[i][0] 是建築編號 / the building id
        r[m].h  = restrictions[i][1];             // restrictions[i][1] 是高度上限 / the height cap
        if (r[m].id == n) hasN = 1;               // 若剛好是最後一棟，記下 / note if it's building n
        m++;
    }
    // 若最後一棟沒被約束，加入一個「幾乎無限」的上限，讓掃描自然算出它的高度。
    // If building n isn't restricted, add a near-infinite cap so the passes compute it.
    if (!hasN) { r[m].id = n; r[m].h = 2000000000L; m++; }

    // 依 id 排序，使相鄰約束在陣列中也相鄰。
    // Sort by id so neighbors are adjacent in the array.
    qsort(r, m, sizeof(Pair), cmp);

    // 左掃：高度不能比「左鄰高度 + 兩者距離」還高（每步最多 +1）。
    // Left pass: a height can't exceed left-neighbor's height + their distance.
    for (int i = 1; i < m; i++)
        r[i].h = lmin(r[i].h, r[i-1].h + (r[i].id - r[i-1].id));

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

    // 對每對相鄰約束算峰值，取全域最大。
    // For each adjacent pair compute the peak; keep the global max.
    long best = 0;
    for (int i = 0; i + 1 < m; i++) {
        long d = r[i+1].id - r[i].id;             // 兩棟之間的距離 / distance between the two
        long peak = (r[i].h + r[i+1].h + d) / 2;  // 峰值公式，整數除法向下取整 / peak, floored
        if (peak > best) best = peak;             // 更新答案 / update answer
    }

    free(r);                                      // 釋放配置的記憶體，避免洩漏 / free heap memory
    return (int)best;                             // 結果在 int 範圍內，安全轉回 / fits in int
}