지구 온난화

바이테아사르 교수는 인터바이테오티아 기후 변화 위원회에 제출할 보고서를 준비하고 있다. 이 보고서는 바이테오티아 주민이 이 지역의 기후 변화에 끼친 영향을 분명하고 의심할 여지 없이 보여 주어야 한다. 교수에게는 실증 자료가 많지만, 주류 언론까지 파고들려면 실질적인 논거를 내놓는 것만으로는 부족하다. 자료를 명확하게, 목적에 맞게 보여 주는 일도 그만큼 중요하다. 그래서 교수는 보고서의 핵심 그래프에 실을 자료를 신중하게 고르려 한다.

핵심 그래프에는 여러 해에 걸친 연평균 기온이 들어간다. 교수에게는 최근 $n$년의 연평균 기온 자료가 있다. 교수는 이 그래프에 "$r_{\min}$년에 기온이 가장 낮았고 $r_{\max}$년에 가장 높았으므로 ...는 명백하다"라는 설명을 붙이고 싶다. 그런데 같은 최저 기온이나 최고 기온이 이 기간에 여러 번 나타날 수 있고, 그러면 설명의 명확성이 흔들릴까 걱정이다.

그래서 교수는 자료의 일부만 그래프에 싣기로 했다. 연도 구간을 하나 골라서, 그 구간 안에서 기온이 가장 낮은 해가 정확히 하나, 기온이 가장 높은 해가 정확히 하나가 되도록 하려는 것이다. 여기서 최저와 최고는 전체 $n$년이 아니라 고른 구간 안에서의 최저와 최고를 뜻한다. 고른 구간이 최근 $n$년 전체에서 기온이 가장 높은 해나 가장 낮은 해를 포함하지 않아도 된다. 물론 교수는 되도록 많은 자료를 싣고 싶으므로, 조건을 만족하는 가장 긴 연도 구간을 찾으려 한다.

첫째 줄에 교수가 연평균 기온을 알고 있는 햇수 $n$ ($1 \le n \le 500\,000$)이 주어진다. 둘째 줄에 $n$개의 정수 $t_1, t_2, \ldots, t_n$ ($-10^9 \le t_i \le 10^9$)이 주어진다. $t_i$는 $i$번째 해의 연평균 기온이다.

두 정수 $l$과 $k$를 출력한다. $l$은 교수의 조건을 만족하는 가장 긴 구간의 길이(햇수)이고, $k$는 조건을 만족하는 길이 $l$의 구간이 시작할 수 있는 가장 이른 해이다. 해는 1번부터 센다.

예제에서 그래프에는 4번째 해부터 9번째 해까지의 기온 5, 2, 3, 4, 6, 3이 실린다. 이 구간에는 구간 최저 기온 2인 해가 정확히 하나, 구간 최고 기온 6인 해가 정확히 하나 있다.