2-4 D.魔法學院與咖啡山

D.魔法學院與咖啡山
Problem ID: cafemountain

    NPSC 魔法學院在 2017 年正式成立囉！相信各位應該多少有點耳聞？

    現在， NPSC 魔法學院已經正式營運兩年了！

    埃迪身為 NPSC 魔法學院的第一任及第二任校長，希望能為魔法學院奠定許多良好的基礎。

    2017 年時，埃迪曾提出一個「魔法學院第一屆的班級數量與學生人數的關係將會是決定校內魔力源是否穩定的關鍵」的重要決策，而在今年 2019 年，埃迪再次做出一個重大的決定，他要用他強大的魔力，將魔法學院移動到咖啡山（Cafe Mountain）的旁邊！

    比起咖啡山，也許你更好奇，為什麼埃迪會當連續兩任的校長呢？但是我認為，這個問題的答案在你我心裡之中就好了！咖啡山在現在更重要一些！

    咖啡山是一座充滿神力的山，只要魔法學院坐落於山旁，便有機會獲得更加穩定且強大的魔力源，這麼好的事情埃迪怎麼會不去追求呢？

    然而事情總不會那麼美好，埃迪想追求，但咖啡山的山神 – A 塔，偏偏不讓他輕易達成。A 塔跟埃迪說：「如果你要把你的學校搬來咖啡山旁，可以，但是你得幫咖啡山完成一件事情！」

    A 塔表示，現在咖啡山上有 n 隻牛排成一排，每隻牛都有他所在的海拔高度，從左到右分別為 a1, a2, . . . , an，且每隻牛的顏色不是黑色（黑牛， Black Cow）就是白色（白牛， White Cow）。白牛兩兩之間是合群的，但是黑牛不是，如果兩隻黑牛在相鄰的兩個位置，也就是分別在從左到右的第 i 隻以及第 i + 1 隻，那麼他們兩隻將會打架！黑牛之間的打架非常特別：對於兩隻相鄰（假設為從左到右第 i 隻及第 i + 1 隻）的黑牛，所在的海拔高度比較高（假設為h = max(ai, ai+1)）的那隻黑牛會往旁邊丟一顆大石頭，壓在另外那隻所在的海拔高度比較低（假設為 l = min(ai, ai+1)）的黑牛身上。眾所皆知的事情是，牛的耐壓程度是有上限的。假設牛的耐壓程度是 K（每一隻牛的耐壓程度都一樣），那麼如果 h - l > K，所在的海拔高度比較低的那隻黑牛會被壓傷！而咖啡山上的牛受傷將會是一件對 A 塔極度不敬的事情之一。特別地，如果兩隻黑牛的海拔高度一樣，那麼這兩隻牛將不會互相傷害喔！
現在， A 塔可以運用他的神力將每隻牛的順序調換（但是每個位置的高度保持不變，也就是說，調換順序後從左到右每隻牛所在的海拔高度仍然是 a1, a2, . . . , an），也可以改變牛的耐壓程度 K。然而改變牛的耐壓程度是一件非常消耗神力的事情，於是 A 塔要埃迪找出最小的牛的耐壓程度 K，使得存在一種方式調換牛的順序之後，沒有任何一隻牛有可能被壓到受傷。

Input

輸入第一行有一個整數 n，代表咖啡山上有 n 隻牛。

之後會有 n 行，每一行有兩個整數 ci, ai，其中 ci 為 0 或 1：如果 ci = 0，代表一開始第 i 隻牛是白牛。反之，若 ci = 1，代表一開始第 i 隻牛是黑牛。 ai 代表的是第 i 隻牛所在的海拔高度。

• 1 ≤ n ≤ 2 × 105
• ci = 0 或 ci = 1，對所有正整數 i ≤ n
• -109 ≤ ai ≤ 109，對所有正整數 i ≤ n

Output

輸出一個整數，代表最小的耐壓程度 K，使得存在一種方式調換牛的順序之後，沒有任何一隻牛有可能被壓到受傷。