Bob's teachers have conspired to give Bob a major assessment in each of their classes on the same day! Bob has classes and has estimated how much he will suffer from each assessment. He has recorded these estimates in an array of positive integers . He defines the **suffering** of a subarray to be the **product** of the minimum element in this subarray and the total sum of the subarray. Given queries of the form `l r`

, output the greatest suffering of any subarray contained in the subarray from to inclusive where the indices are 1-indexed.

#### Constraints

##### Subtask 1 [4%]

##### Subtask 2 [15%]

##### Subtask 3 [17%]

There are at most different values of

##### Subtask 4 [24%]

There are at most different values of

##### Subtask 5 [40%]

No additional constraints

#### Input Specification

The first line will contain two space-separated integers, and .

The next line will contain space-separated integers, .

The next lines will each contain a query of the form `l r`

.

#### Output Specification

For each of the queries, output a single integer, the largest suffering of a subarray contained in the queried subarray.

#### Sample Input 1

```
6 4
3 5 2 3 5 1
2 2
1 3
1 4
2 6
```

#### Sample Output 1

```
25
25
26
30
```

#### Explanation for Sample 1

For the first query, the subarray gives a suffering of

For the second query, the subarray gives a suffering of

For the third query, the subarray gives a suffering of

For the fourth query, the subarray gives a suffering of

#### Sample Input 2

```
5 10
1 2 2 3 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
```

#### Sample Output 2

```
4
8
14
25
8
14
25
10
25
25
```

#### Sample Input 3

```
10 12
8 2 5 4 1 5 9 8 7 3
1 10
2 4
3 7
7 9
4 6
2 3
7 7
5 10
3 3
1 4
6 8
2 8
```

#### Sample Output 3

```
168
36
81
168
25
25
81
168
25
64
136
136
```

## Comments