You are given a permutation $P$ of the integers $1$ to $N$.

We define the value of any non-empty contiguous subarray in $P$ as its product divided by its length.

More formally, the value of some range $[l,r]$ is $\frac{P_l\times P_{l+1}\times \dots \times P_r}{r-l+1}$.

Find a subarray $[l,r]$ that results in the maximum possible value.

Constraints

$1\le N\le 2\times {10}^5$

$1\le P_i\le N$

$P$ is a permutation of $1,2,\dots ,N$.

Subtask 1 [20%]

$N\le 15$

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line of input contains an integer $N$.

The next line of input contains $N$ space-separated integers representing $P$.

Output Specification

Output $2$ space-separated integers $l$ and $r$, representing any maximum value subarray $[l,r]$.

Sample Input

4
3 1 4 2

Sample Output

1 4