Uitându-ne din New Jersey către New York, Manhattan, departe, în zare, se văd zgârie norii. De la distanță, nu distingem clădirile, ci numai o linie formată din segmente orizontale și verticale, așa numita skyline.

Cerința

Determinați care este aria celui mai mare dreptunghi care se poate înscrie în skyline.

Date de intrare

Prima linie a fișierului skyline.in va conține numărul n de segmente orizontale din linie. Pe următoarele n linii vor fi trecute perechi de numere h l, reprezentând înălțimea și lungimea fiecărui segment.

Date de ieșire

Fișierul de ieșire skyline.out va conține un singur număr, aria celui mai mare dreptunghi conținut în skyine.

Restricții și precizări

• 1 ≤ n ≤ 40.000;
• 0 ≤ h ≤ 2.000.000.000;
• 1 ≤ l ≤ 50.000;
• Dreptunghiul maximal are laturile verticale şi orizontale.

Exemplu

skyline.in

7
4 3
11 6
8 2
9 4
2 2
4 9
8 9

skyline.out

96

Explicație

Cel mai mare dreptunghi care se poate înscrie începe la coordonatele (3, 0) şi are laturile de lungime 12 şi 8.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("skyline.in");
ofstream cout("skyline.out");

int s[40005] , d[40005] , h[40005] , n , Q[40005] , vf;
long long l[40005] , maxi;

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> h[i] >> l[i];
        l[i] = l[i] + l[i - 1];
    }
    vf = 0;
    Q[0] = n + 1;
    for(int i = n ; i >= 1 ; i--)
    {
        while(vf > 0 && h[i] <= h[Q[vf]]) vf--;
        d[i] = Q[vf];
        Q[++vf] = i;
    }
    vf = 0;
    Q[0] = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        while(vf > 0 && h[i] <= h[Q[vf]]) vf--;
        s[i] = Q[vf];
        Q[++vf] = i;
    }
    for(int i = 1 ; i <= n ; i++)
        maxi = max(maxi , h[i] * (l[d[i] - 1] - l[s[i]]));
    cout << maxi;
}