Background

Your useless classmate is stuffing your head with meaningless information, so you decide you’re done with him.

Problem Description

Specifically, your classmate said $n$ pieces of nonsense. The $i$-th piece contains information amount $a_i$, so what he said can be seen as a sequence of length $n$: $a_1 \dots a_n$.

Define the information density of an interval $[l, r]$ as the total information amount in this interval divided by the interval length. That is, the information density of $a_{[l \dots r]}$ is $\dfrac{\sum_{i=l}^{r} a_i}{r - l + 1}$.

To be done with your classmate, you decide to find the consecutive segment of his words with the lowest information density. In other words, you need to find a subinterval of the sequence such that the information density of this interval is minimized.

To avoid letting your classmate notice that you are picking a fight, this information density cannot be $0$.

Input Format

The first line contains an integer $n$, representing the number of nonsense statements your classmate said.

The second line contains $n$ space-separated integers $a_1 \dots a_n$, representing the information amount of each statement.

Output Format

Output one line with two positive integers $x, y$ separated by a space, meaning that among all consecutive segments with non-zero information density, the minimum information density is $\dfrac{x}{y}$.

Note that the fraction $\dfrac{x}{y}$ must be in lowest terms. In particular, if after simplification the result is an integer, then $y = 1$.

5
0 2 0 1 0

1 3

Hint

This problem uses bundled testdata.

Special property: It is guaranteed that there is only one value in the sequence that is greater than $0$.

For all testdata, it is guaranteed that:

$1 \le n \le 10^6$, $0 \le a_i \le 10^9$, and the maximum value of the sequence is non-zero.

Translated by ChatGPT 5