Singularity Cup P1 - Maximum Permutation Product

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

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 \ldots \times P_r}{r-l+1}.

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


1 \le N \le 2\times10^5

1 \le P_i \le N

P is a permutation of 1, 2, \ldots, 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

3 1 4 2

Sample Output

1 4


There are no comments at the moment.