#CS1142. 广告

广告

题目背景

翻译自 CSES-1142 题。

题目描述

一个围栏由 n 根垂直的木板组成。每根木板的宽度为 1，木板的高度可能不同。

你想在围栏上附上一个矩形广告，问这个广告的最大面积是多少？

输入格式

第一行包含一个整数 n，表示围栏的宽度（即木板的数量）。

第二行包含 n 个整数 k1,k2,…,knk_1, k_2, \dots, k_nk1​,k2​,…,kn​，分别表示每根木板的高度。

输出格式

输出一个整数：表示矩形广告的最大面积。

样例

8
4 1 5 3 3 2 4 1

10

说明/提示

$1 \leq n \leq 2 \times 10^5$

1≤ki≤1091 \leq k_i \leq 10^91≤ki​≤109。