H. Histogram in 3D
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

"Largest Rectangle in Histogram" problem is a classic problem. You are given an array of integers $$$arr$$$ where each element represents the height of a bar in a histogram. A histogram is a graphical display of data using bars of different heights. The bars are placed in the exact same sequence as given in the array, and each of them has width $$$1$$$. You need to find the area of the largest rectangle in the histogram.

But now, Cuber QQ wants to generalize this problem to three-dimensional case: Given an array of pairs, each of which represents a bar's depth and height. The bars have their front side aligned and each of them has width $$$1$$$. Please find the largest volume of the sub-cuboid in the 3D-histogram.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$), the number of blocks.

The next $$$n$$$ lines each contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i,y_i \le 10^6$$$), the $$$i$$$-th block's depth and height.

Output

The output is a single integer in one single line, the largest volume.

Examples
Input
3
1 1
3 3
2 2
Output
9
Input
5
4 3
5 6
2 4
1 5
3 2
Output
30
Note

The figure shows the 3D-histogram for the first sample.