Maximum Interval Weight in a Permutation

You are given a permutation a of length \(n\). Consider all \(\frac{n(n+1)}{2}\) contiguous subarrays (intervals) \([l, r]\) of the permutation. For each interval, its weight is defined as follows:

• Let \(x = r - l + 1\) be the length of the interval.
• Sort the numbers in the interval in increasing order. Let \(y\) be the median of this sorted sequence. Note that the median is defined as follows:

For a strictly increasing sequence of length \(m\):

• If \(m\) is odd, the median is \(a_{\frac{m+1}{2}}\).
• If \(m\) is even, the median is \(\frac{a_{\frac{m}{2}}+a_{\frac{m}{2}+1}}{2}\).

Then the weight of the interval is defined as:

[ \text{weight} = x + 2y, ]

Note that if \(m\) is even, \(2y = a_{\frac{m}{2}} + a_{\frac{m}{2}+1}\), so the weight is always an integer.

Your task is to compute the maximum weight among all intervals and the number of intervals that achieve this maximum weight.

inputFormat

The first line contains an integer \(n\) (the length of the permutation). The second line contains \(n\) space-separated integers representing the permutation \(a\). It is guaranteed that \(a\) is a permutation of \(\{1, 2, \dots, n\}\).

outputFormat

Output two space-separated integers: the maximum weight among all intervals and the number of intervals that achieve this maximum weight.

sample

3
1 2 3

7 3