3차원 히스토그램

말나르 씨 (전화 통화): 들어 보세요. 한밤중에 자그레브 곳곳에 포스터를 붙여야 했어요. 높이가 제각각인 널빤지로 된 울타리를 봤는데, 이 울타리에 들어가는 포스터의 최대 넓이를 어떻게 구할지 고민이 되더군요. 이거 좋은 COCI 문제가 되지 않을까요?

동료: 뭘 하셨다고요?! 어쨌든 이 문제는 별로예요. 단조 큐를 쓰는 표준 기법이라서, 우리 캠프에서는 초등학생에게도 가르치는 내용이에요.

말나르 씨: 조금 비틀어서 모든 접두사마다 답을 구하라고 하면 어떨까요? 그 정도면 충분히 어려울 것 같은데요.

동료: 바로 그 문제가 작년 CERC 예선에 나왔어요. 어려운 문제였고 결국 Harbingers 기법으로 풀리는데, 이제는 다들 본 문제예요.

말나르 씨: 정말 할 수 있는 게 없을까요?

동료: 히스토그램 문제는 거의 다 나왔다고 봐요. COCI 2010/2011 (Tabovi), COCI 2015/2016 (Poplava), COCI 2017/2018 (Krov), IOI 선발 시험 2018 (Histogram)... 무슨 말인지 아시죠.

말나르 씨: 히스토그램이 3차원이면 어떨까요?

동료: 음...

3차원 히스토그램이 주어집니다. 이 히스토그램은 $n$개의 블록이 옆으로 붙어 있는 구조입니다. $i$번째 블록은 너비가 1미터, 높이가 $a_i$미터, 길이가 $b_i$미터입니다. 앞에서 보면 높이가 $a_1, a_2, \ldots, a_n$인 막대그래프처럼 보이고, 위에서 보면 높이가 $b_1, b_2, \ldots, b_n$인 막대그래프처럼 보입니다.

주어진 3차원 히스토그램 안에 놓을 수 있는 부피가 가장 큰 직육면체를 구하세요. 직육면체의 각 면은 히스토그램을 이루는 블록의 면과 평행해야 합니다.

첫 줄에 정수 $n$이 주어집니다. 이어지는 $n$개의 줄 중 $i$번째 줄에는 정수 $a_i$와 $b_i$가 주어집니다 ($1 \le a_i, b_i \le 10^6$).

직육면체의 부피를 세제곱미터 단위로 출력하세요.

첫 번째 예제에 대한 설명:

가장 큰 직육면체는 처음 두 블록의 일부를 사용합니다. 너비 2미터, 높이 4미터, 길이 3미터이며, 부피는 $2 \times 4 \times 3 = 24$세제곱미터입니다.