問題文

無限に長い数直線上のシーソーがあり、各地点には整数座標が割り当てられています。 このシーソーに対して、$N$ 個の「コイン落下イベント」が発生します。$i$ 番目のイベント $(1 \le i \le N)$ は $(t_i, x_i)$ で表され、時刻 $t_i$ に位置 $x_i$ に新しいコインが 1 枚追加されることを意味します。

あなたは、各整数時刻 $t = 1, 2, \dots, t_N$ において、シーソーに対して以下のいずれかの操作を 1 つ選択して行うことができます。

• 左に傾ける：その時点でシーソー上にあるすべてのコインの座標を $-1$ する。
• 右に傾ける：その時点でシーソー上にあるすべてのコインの座標を $+1$ する。
• 水平に保つ：その時点でシーソー上にあるすべてのコインの座標を変化させない。

各時刻 $t$ における詳細な手順は以下の通りです。

1. もし時刻 $t$ があるイベントの時刻 $t_i$ と一致するなら、その瞬間のシーソーの位置 $x_i$ にコインが追加される。
2. その後、あなたが選択した操作（左に傾ける、右に傾ける、または水平に保つ）を 1 つ実行し、すべてのコインが移動（または静止）する。

すべてのイベントが終了し、時刻 $t_N$ の操作を終えた直後における、シーソー上のすべてのコインの座標の 幅（最大座標 − 最小座標）を考えます。 操作を適切に選択したとき、達成可能な「幅」の最小値を求めてください。

制約

• $1 \le N \le 2 \times 10^5$
• $1 \le t_1 < t_2 < \dots < t_N \le 10^9$
• $-10^9 \le x_i \le 10^9$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

出力

達成可能な最小の幅を 1 行で出力せよ。

サンプル

2
1 0
3 5

3

• 時刻 1：座標 $0$ にコイン 1 が置かれる。その後「右に傾ける」を選択すると、コイン 1 は座標 $1$ に移動する。
• 時刻 2：イベントはない。その後「右に傾ける」を選択すると、コイン 1 は座標 $2$ に移動する。
• 時刻 3：座標 $5$ にコイン 2 が置かれる。その後「右に傾ける」を選択すると、コイン 1 は座標 $3$、コイン 2 は座標 $6$ に移動する。
• 最終的な座標は $\{3, 6\}$ となり、幅は $6 - 3 = 3$ です。これが最小値となります。