Migrated from Lutece 1163 Intervals Query

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Given an Array $A$ with length $N$ ($1 \leq N \leq 5 \cdot 10^5$), find a longest consecutive sub-interval on Array $A$ satisfied that there is no more than 1 minimum number and no more than 1 maximum number in the sub-interval.

Input

The first line contains an integer $N$ ($1 \leq N \leq 5 \cdot 10^5$) meaning the length of Array $A$.

The second line contains $N$ integers $A_1, A_2 , .... ,A_n$ ($-10^9 \leq A_i \leq 10^9$).

Output

Output two integers $L$ and $From$ representing the length of the longest consecutive sub-interval on Array $A$ satisfied the condition and the starting position in Array $A$ (starts from 1).

If there are multiple answers, you can output any of them.

Samples

1
10

1 1

10
8 3 2 5 2 3 4 6 3 6

6 4

10
-1 2 -1 2 1 1 2 -1 0 0

6 5

Resources

2015 UESTC ACM Summer Training Team Selection (4)