Đường tăng dài nhất trên chuỗi cảm biến

Bối cảnh

Một dây chuyền kiểm định ghi lại n giá trị cảm biến theo đúng thứ tự thời gian. Một giai đoạn được xem là "ổn định tăng" nếu các giá trị liên tiếp trong giai đoạn đó tăng nghiêm ngặt: mỗi giá trị sau phải lớn hơn giá trị ngay trước. Kỹ sư cần tìm giai đoạn tăng liên tiếp dài nhất để đối chiếu với thời điểm máy đạt ngưỡng vận hành. Nếu có nhiều giai đoạn cùng độ dài, hệ thống chọn giai đoạn xuất hiện sớm nhất vì đây là tín hiệu đầu tiên cần được điều tra.

Bài toán quen thuộc với mảng một chiều, nhưng tại B13 bạn phải duyệt bằng recursion thay vì vòng lặp chính. Mỗi tầng xử lý một vị trí mới, cập nhật độ dài đoạn tăng hiện tại và so sánh với đáp án tốt nhất. Điểm khó hơn bài Easy nằm ở việc recursion không chỉ trả một con số: bạn phải duy trì đúng trạng thái currentStart, currentLength, bestStart, bestLength qua nhiều tầng mà vẫn bảo đảm tie-break chọn đoạn sớm nhất.

Yêu cầu

1. Đọc n và mảng a.
2. Dùng hàm đệ quy để duyệt từ trái sang phải.
3. Tìm đoạn liên tiếp tăng nghiêm ngặt dài nhất.
4. Nếu hòa độ dài, chọn đoạn có L nhỏ hơn.
5. In length L R với chỉ số 0-based.

Yêu cầu tổ chức code

Phần duyệt và cập nhật đoạn bắt buộc nằm trong hàm đệ quy.

Online Judge chấm output. Giảng viên có thể review source code để xác nhận học viên dùng đúng recursion và không vượt prerequisite.

Input

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

Output

Một dòng length L R.

Ràng buộc

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

Ví dụ 1

Input

8
1 2 5 3 4 6 7 0

Output

4 3 6

Giải thích

Dãy bắt đầu bằng đoạn 1,2,5 tại index 0..2, dài 3. Sau khi gặp 3, đoạn hiện tại được reset ở index 3 và tiếp tục tăng qua 3,4,6,7, tạo đoạn 3..6 dài 4. Vì 4 lớn hơn 3, đáp án tốt nhất được cập nhật thành length=4, L=3, R=6. Phần tử cuối 0 làm đoạn bị ngắt nên không tạo đáp án mới.

Ví dụ 2

Input

5
5 4 3 2 1

Output

1 0 0

Giải thích

Dãy 5 4 3 2 1 không có cặp kề nào tăng nghiêm ngặt. Mỗi khi xét phần tử mới, currentLength trở lại 1. Đáp án khởi tạo là đoạn một phần tử tại index 0 và không bao giờ bị vượt qua. Do quy tắc hòa chọn đoạn xuất hiện sớm nhất, kết quả là 1 0 0.

Thông tin học tập

• Module: M04
• Buổi: B13
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: recursion, static arrays, longest increasing run, state tracking, tie-break
• Giới hạn kiến thức: B01-B13
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100