408187: GYM103048 H Histogram in 3D

"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.

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.

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

3
1 1
3 3
2 2

9

5
4 3
5 6
2 4
1 5
3 2

30

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