CSES 1142 ↗

Advertisement

The largest axis-aligned rectangle fitting under the board heights.

0
submissions
—
best score

A fence consists of n vertical boards. The width of each board is 1 and their heights may vary.

You want to attach a rectangular advertisement to the fence. What is the maximum area of such an advertisement?

Input

The first input line contains an integer n: the width of the fence.

After this, there are n integers k1,k2,…,kn: the height of each board.

Output

Print one integer: the maximum area of an advertisement.

Constraints

  • 1≤n≤2⋅105
  • 1≤ki≤109

Example

Input:

8
4 1 5 3 3 2 4 1

Output:

10

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/Advertisement/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Results

No scoring submissions yet. One counts once the kernel accepts its proof and every test passes.

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.