Đoạn ngắn nhất bao phủ hai cực trị

Bối cảnh

Trong vòng kiểm tra cuối của một hệ thống cảm biến, ban tổ chức cần khoanh vùng một đoạn dữ liệu đủ để quan sát đồng thời cả hai trạng thái "thấp nhất" và "cao nhất" đã xuất hiện trong toàn bộ phiên đo. Mỗi vị trí của mảng là một mốc thời gian; giá trị nhỏ nhất toàn dãy đại diện cho trạng thái cực tiểu và giá trị lớn nhất đại diện cho trạng thái cực đại.

Để giảm lượng dữ liệu phải trích xuất, cần chọn đoạn liên tiếp ngắn nhất chứa ít nhất một lần xuất hiện của cực tiểu và ít nhất một lần xuất hiện của cực đại. Nếu có nhiều đoạn cùng độ dài nhỏ nhất, chọn đoạn có chỉ số trái nhỏ hơn. Trường hợp đặc biệt toàn bộ dãy có cùng giá trị thì cực tiểu và cực đại trùng nhau; một phần tử bất kỳ đã đủ, và theo quy tắc phá hòa phải chọn vị trí 0.

Điểm khó không nằm ở việc tìm min/max mà ở việc không thử mọi cặp vị trí. Khi quét từ trái sang phải, chỉ lần xuất hiện gần nhất của min và max mới có khả năng tạo đoạn ngắn nhất kết thúc tại vị trí hiện tại.

Yêu cầu

1. Tìm giá trị nhỏ nhất và lớn nhất toàn mảng.
2. Quét lại mảng, lưu vị trí gần nhất của min và max.
3. Mỗi khi đã có cả hai vị trí, tạo đoạn giữa chúng và cập nhật đáp án theo độ dài rồi theo chỉ số trái.

Input

Dòng 1: n. Dòng 2: n số nguyên.

Output

Một dòng length L R, với L,R là chỉ số 0-based của đoạn được chọn.

Ràng buộc

1 ≤ n ≤ 2000, |a[i]| ≤ 10^9.

Ví dụ 1

Input

8
4 1 7 3 7 2 1 5

Output

2 1 2

Giải thích

Toàn dãy có min 1 tại các index 1, 6 và max 7 tại các index 2, 4. Khi quét từ trái sang phải, ngay tại index 2 ta đã có lần xuất hiện gần nhất của min ở index 1 và max ở index 2, tạo đoạn [1,2] dài 2. Các cặp cực trị xuất hiện sau đó chỉ tạo đoạn dài hơn, ví dụ [4,6] dài 3. Vì không thể có đoạn chứa cả hai giá trị khác nhau mà ngắn hơn 2 phần tử, đáp án tối ưu là length=2, L=1, R=2.

Ví dụ 2

Input

5
9 9 9 9 9

Output

1 0 0

Giải thích

Mọi phần tử đều bằng 9, nên min và max của toàn dãy cùng bằng 9. Khi hai cực trị trùng nhau, chỉ cần một phần tử đã đồng thời chứa cả min lẫn max; độ dài tối ưu vì thế là 1. Có nhiều đoạn một phần tử cùng tối ưu, nên quy tắc phá hòa chọn chỉ số trái nhỏ nhất là 0, cho kết quả 1 0 0.

Thông tin học tập

• Module: M03
• Buổi: B09
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: static arrays, global min max, latest positions, shortest segment, tie-break
• Giới hạn kiến thức: B01-B09
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100