配点 : $700$ 点

問題文

$2$ 個の白いボールが入った袋が $N$ 個あります。$i$ 個目の袋にはそれぞれ整数 $x_i$ と $y_i$ が書かれたボールが $1$ 個ずつ入っています。

あなたはこの袋それぞれについて、片方のボールを赤く塗り、もう片方を青く塗ります。

そのあと $2N$ 個のボールを、塗られた色で分類します。

そして

• 赤く塗られたボールに書かれた整数の最大値を $R_{max}$
• 赤く塗られたボールに書かれた整数の最小値を $R_{min}$
• 青く塗られたボールに書かれた整数の最大値を $B_{max}$
• 青く塗られたボールに書かれた整数の最小値を $B_{min}$

としたときに、$(R_{max} - R_{min}) \times (B_{max} - B_{min})$ の最小値を求めてください。

制約

• $1 \leq N \leq 200,000$
• $1 \leq x_i, y_i \leq 10^9$

入力

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

$N$

$x_1$ $y_1$

$x_2$ $y_2$

:

$x_N$ $y_N$

出力

問題の答えを出力する。

3
1 2
3 4
5 6

15

$x_1$, $x_2$, $y_3$ の書かれたボールを赤色に塗り、 $y_1$, $y_2$, $x_3$ の書かれたボールを青色に塗ると最適解になります。

3
1010 10
1000 1
20 1020

380

2
1 1
1000000000 1000000000

999999998000000001