Peak Product - MarisaOJ: Marisa Online Judge

Peak Product

Time limit: 1000 ms
Memory limit: 256 MB
Consider an array $A$ consisting of $n$ integers. We define the function $f(l,r)$ as follows: $$f(l,r) = (r - l + 1) \times min(A_l,A_{l+1},...,A_r)$$ Our goal is to find the maximum value of $f(l,r)$ with $1 \leq l \leq r \leq n$. ### Input - The first line contains an integer $n$. - The second line contains $n$ integers $A_i$. ### Output - Print an integer is the maximum possible $f(l,r)$. ### Constraints - $1 \le n \le 10^5$. - $1 \le A_i \le 10^9$. ### Example Input: ``` 3 1 2 3 ``` Output: ``` 4 ```