- Prepare
- Algorithms
- Constructive Algorithms
- Two Subarrays

# Two Subarrays

# Two Subarrays

Consider an array, , of integers. We define the following terms:

**Subsequence**

A subsequence of is an array that's derived by removing zero or more elements from without changing the order of the remaining elements. Note that a subsequence may have zero elements, and this is called*the empty subsequence*.**Strictly Increasing Subsequence**

A non-empty subsequence is*strictly increasing*if every element of the subsequence is larger than the previous element.**Subarray**

A subarray of is an array consisting of a contiguous block of 's elements in the inclusive range from index to index . Any subarray of can be denoted by .

The diagram below shows all possible subsequences and subarrays of :

We define the following functions:

- = the maximum sum of some
*strictly increasing subsequence*in subarray

We define the *goodness*, , of array to be:

In other words, is the maximum possible value of for all possible subarrays of array .

Let be the length of the smallest subarray such that . Given , find the value of as well as the number of subarrays such that and , then print these respective answers as space-separated integers on a single line.

**Input Format**

The first line contains an integer, , denoting number of elements in array .

The second line contains space-separated integers describing the respective values of .

**Constraints**

**Subtasks**

For the of the maximum score:

For the of the maximum score:

**Output Format**

Print two space-seperated integers describing the respective values of and the number of subarrays satisfying and .

**Sample Input 0**

```
3
2 3 1
```

**Sample Output 0**

```
1 1
```

**Explanation 0**

The figure below shows how to calculate :

is the length of the smallest subarray satisfying . From the table, we can see that . There is only one subarray of length such that .