Bajtek runs an online store. His customers are usually very satisfied and leave very positive reviews online. Unfortunately, it sometimes happens that someone, for reasons known only to them, leaves a false and negative review. Perhaps the person was in a bad mood, perhaps they confused Bajtek's store with another similar one, or perhaps they were angry at Bajtek because he did not agree to sell a product at a reduced price?

In the online ranking that interests Bajtek, every user can rate the store with a single integer. Bajtek's store has already received $n$ ratings: $a_1, a_2, \dots, a_n$. The ratings are ordered in the order they were given, from the earliest to the latest. Interestingly, it turned out that each of the ratings from $1$ to $n$ appeared in the history exactly once!

In addition to the raw data, the site also displays a summary of all ratings – the number $n$ of all ratings and their median. The median is determined in the online ranking using the standard method. The sequence of ratings is first sorted in non-decreasing order: $a'_1 \le a'_2 \le \dots \le a'_n$. Then:

• If the number of ratings is odd, the median is the middle value in the sorted sequence, i.e., $a'_{\frac{1}{2}(n+1)}$.
• If the number of ratings is even, the median is the arithmetic mean of the two middle values in the sorted sequence, i.e., $\frac{1}{2}(a'_{\frac{1}{2}n} + a'_{\frac{1}{2}n+1})$.

Since Bajtek received each rating from $1$ to $n$ inclusive exactly once, it is easy to calculate that the median of all the store's ratings is currently exactly $\frac{1}{2}(n + 1)$.

A hacker from Bajtek's company managed to break into the ranking system, which gives him the ability to influence some of its parameters. In particular, he is able to remove some of the oldest ratings and some of the newest ratings of Bajtek's store. More precisely, the hacker can choose two integer parameters $\ell$ and $r$ ($1 \le \ell \le r \le n$) and leave only the ratings $a_\ell, a_{\ell+1}, \dots, a_r$ in the ranking system. Then the ranking system will update the number and the median of all remaining ratings.

Furthermore, the hacker learned from the system's source code that stores that maximize the objective function, equal to the sum of the number of ratings and twice the median of the ratings (that is, $X + 2 \cdot Y$, where $X$ is the number of ratings and $Y$ is the median of the ratings), are displayed higher on the main ranking page. It is easy to notice that the objective function is always an integer, regardless of the number and median of the ratings.

Help Bajtek position his store in the ranking system! Determine the maximum possible value of the objective function after the hacker's intervention. Also, state how many different ways the hacker can achieve this objective function value. Two ways are considered different if at least one of the parameters $\ell, r$ is different in both ways.

Input

The first line of input contains a single integer $n$ ($1 \le n \le 10^6$). The second line contains $n$ integers $a_1, \dots, a_n$ ($1 \le a_i \le n$) representing the individual store ratings. Each of the ratings from $1$ to $n$ appears in the sequence exactly once.

Output

The output should contain two integers – the maximum value of the objective function after the hacker's attack and the number of different ways this value can be achieved.

Examples

Input 1

5
1 4 3 5 2

Output 1

11 5

Note

Explanation of the example: To obtain an objective function value equal to 11, the hacker can choose the following pairs of parameters $(\ell, r)$:

• $(1, 4)$ – the remaining ratings are $1, 4, 3, 5$, so the number of ratings is $X = 4$ and the median is $Y = \frac{7}{2}$.
• $(1, 5)$ – the remaining ratings are $1, 4, 3, 5, 2$. We then have $X = 5$ and $Y = 3$.
• $(2, 4)$ – the remaining ratings are $4, 3, 5$. We then have $X = 3$ and $Y = 4$.
• $(2, 5)$ – the remaining ratings are $4, 3, 5, 2$. We then have $X = 4$ and $Y = \frac{7}{2}$.
• $(4, 4)$ – only the rating $5$ remains. We then have $X = 1$ and $Y = 5$.

In each of the above cases, the objective function has a value of $X + 2 \cdot Y = 11$.