# Programming contests

## DEIK Regionális Programozó Csapatverseny, egyetemi kategória, 2022. december 4.

December 4, 2022 10:00 AM – December 4, 2022 3:15 PM

# spaceship

The vogon spaceships have a peculiar velocity-control: a large number of buttons in a row, each of which is labelled with a positive integer: `s1,...,sN`. The mode of operation is the following: the vogon pilot clears the current setting (it means that all the buttons gets into the state `OFF`), then he chooses a continous sequence of buttons: `si,si+1,...,sj, (i≤j)`, then he pushes all of these buttons to `ON` state. Finally he pushes the main-button. The result of this (sometimes very long) procedure that the ship accelerates/decelerates to the velocity given by the formula: ``` ```

``` (j-i+1)*min({si,...,sj}) ```
``` ``` Your task is to compute the maximal possible velocity of the ship (M).

## Example

```    N: 4
The numbers on the buttons are: 4,1,2,3
By exploring every possible choice, we see that the maximal velocity is `4`:
```
```        i,j    v
--------
1,1 -> 4
1,2 -> 2
1,3 -> 3
1,4 -> 4
2,2 -> 1
2,3 -> 2
2,4 -> 3
3,3 -> 2
3,4 -> 4
4,4 -> 3
```

## Input Specification

``````
N
s1 ... sN
```
```

The first line is the number `1 ≤ N ≤ 105 ` of the buttons the ship has. The space seaparated numbers `1 ≤ sk ≤ 109 (k=1...N) ` come in the second line.

## Output Specification

```M
```

A line with the maximal velocity `M`.

## Sample Input 1

1. `4`
2. `4 1 2 3`

## Sample Output 1

1. `4`
1. `4`
2. `3 2 2 1`
1. `6`