Dãy \(B = \{ b_{1},\ b_{2},\ldots,b_{m}\}\) được gọi là dãy con của \(A\) khi \(b_{1} = a_{i};\ b_{2} = a_{i + 1};\ldots;b_{m} = a_{i + m - 1}\) với \(i \geq 1\) và \(m \leq n\).

Cho số nguyên dương \(n\) và dãy \(A = \{ a_{1},\ a_{2},\ldots,a_{n})\), hãy tìm dãy \(B\) là dãy con tăng \((b_{i} < b_{i + 1})\) dài nhất của \(A\), nếu có nhiều dãy \(B\) thỏa mãn điều kiện thì đưa ra dãy con dài nhất có chỉ số cuối lớn nhất

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(n\ (n \leq 10^{6})\)

+ Dòng thứ 2 ghi \(n\) số nguyên dương \(a_{1},\ a_{2},\ldots,a_{n}\ (|a_{i}| \leq 10^{9})\)

Dữ liệu ra:

+ Ghi hai số nguyên \(vt_{1}\) và \(vt_{2}\) lần lượt là vị trí đầu tiên và vị trí cuối cùng của dãy con tìm được

Ví dụ:

Input	Output
8 2 5 3 6 8 9 3 7	3 6