Mr. Malnar (over the phone): Listen, I had to put up some posters around Zagreb in the middle
of the night. I stumbled upon a fence that was made out of some planks of varying heights, and I was
thinking about how to calculate the largest area of a poster that I can fit on the fence. Wouldn’t that
make a nice COCI problem?
Associate: You were doing what?! Anyway, the problem is no good. It’s a standard trick with a monotone
queue, we even teach that to elementary school students on our camps.
Mr. Malnar: What if you twist it a bit, ask for the answer for every prefix or something like that, that
should be hard enough.
Associate: That exact problem was featured last year in our CERC qualification contest. A tough one,
it boils down to the Harbingers trick, but now everyone has seen it.
Mr. Malnar: Are you sure there is nothing we can do?
Associate: I think we have exhausted all problems with histograms. COCI \(2010/2011\) (Tabovi), COCI
\(2015/2016\) (Poplava), COCI \(2017/2018\) (Krov), IOI selection test 2018 (Histogram)... You get the point.
Mr. Malnar: What if the histogram is thr\(ee-di\)mensional?
Associate: Umm...
You are given a 3D histogram, that consists of \(n\) blocks that are placed next to each other. The \(i-th\)
block is 1 meter wide, \(a@@RISE_MATH_BLOCK_0@@i\) meters long. In other words, from the front it looks like a
histogram with bars of heights \(a_{1}\), a_{2}, . . . a_{n}, and from the top it looks like a histogram with bars of heights
\(b\)1, b2, . . . b\(n\).
Determine the block with maximum volume that can be placed inside the given 3D histogram. The
sides of that block need to be parallel with the sides of the blocks that make up the 3D histogram.

Subtask 1 (20 points): \(1 \le n \le 2000\)

Subtask 2 (90 points): \(1 \le n \le 200\,000\)

The first line contains the integer \(n\) from the task description.
The \(i-th\) of the following \(n\) lines contains integers \(a_{i}\) and \(b_{i}\) (\(1 \le a_{i}\), \(b_{i} \le 10^{6}\)) from the task description.

Print the volume in cubic meters.

생성자가 기록되지 않았습니다.

출처 COCI 2020/2021 Contest 1