Đoạn núi dài nhất

Bối cảnh

Trong một bài phân tích địa hình, dãy độ cao của n điểm được đo theo thứ tự từ trái sang phải. Một đoạn liên tiếp được gọi là đoạn núi nếu tồn tại đúng một đỉnh p nằm bên trong đoạn sao cho độ cao tăng nghiêm ngặt từ đầu đoạn đến p, sau đó giảm nghiêm ngặt từ p đến cuối đoạn. Cả sườn tăng và sườn giảm phải có ít nhất một bước, vì vậy đoạn chỉ tăng hoặc chỉ giảm không được xem là núi.

Nhiệm vụ là tìm đoạn núi dài nhất. Nếu có nhiều đoạn cùng độ dài, chọn đoạn bắt đầu sớm hơn. Nếu dãy không chứa đoạn núi hợp lệ, in 0 -1 -1.

Một cách thử mở rộng từ mọi đỉnh có thể dẫn đến nhiều phép so sánh lặp lại. Bài Advanced yêu cầu nhận ra rằng thông tin "đang tăng được bao lâu" và "sẽ giảm được bao lâu" có thể được tiền xử lý bằng chính mảng và các vòng lặp đã học, không cần thuật toán hay cấu trúc dữ liệu của buổi sau.

Đây là bài Hard vì cần tách một điều kiện hình học thành hai đại lượng cục bộ và ghép chúng tại mỗi đỉnh, thay vì viết ba vòng lặp thử mọi đoạn.

Yêu cầu

1. Tạo inc[i]: độ dài đoạn tăng nghiêm ngặt dài nhất kết thúc tại i.
2. Tạo dec[i]: độ dài đoạn giảm nghiêm ngặt dài nhất bắt đầu tại i.
3. i là đỉnh hợp lệ nếu cả hai >=2; đoạn núi là phần ghép của hai dãy con.
4. Cập nhật đoạn dài nhất, tie theo L.

Input

Dòng 1: n. Dòng 2: n độ cao.

Output

Một dòng length L R; nếu không có đoạn núi hợp lệ, in 0 -1 -1.

Ràng buộc

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

Ví dụ 1

Input

9
1 2 3 5 4 2 1 3 2

Output

7 0 6

Giải thích

Đoạn từ index 0 đến 6 là 1,2,3,5,4,2,1. Nó tăng nghiêm ngặt 1<2<3<5 đến đỉnh tại index 3, sau đó giảm nghiêm ngặt 5>4>2>1, nên đây là một đoạn núi hợp lệ dài 7. Đoạn 1,3,2 ở cuối dãy (index 6..8) cũng là núi nhưng chỉ dài 3. Khi xây inc[3]=4 và dec[3]=4, công thức ghép cho độ dài 4+4-1=7, suy ra L=0, R=6. Không có đỉnh nào tạo đoạn dài hơn nên output là 7 0 6.

Ví dụ 2

Input

5
1 2 3 4 5

Output

0 -1 -1

Giải thích

Dãy 1 2 3 4 5 chỉ tăng nghiêm ngặt và không hề có bước giảm sau một đỉnh. Với mọi vị trí, nếu inc[i] đủ lớn thì dec[i] chỉ bằng 1, nên điều kiện một đỉnh phải có cả sườn tăng và sườn giảm đều không thỏa. Vì không tồn tại đoạn núi hợp lệ, đề yêu cầu in giá trị đặc biệt 0 -1 -1.

Thông tin học tập

• Module: M03
• Buổi: B09
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: static arrays, increasing run, decreasing run, auxiliary arrays, longest mountain, tie-break
• Giới hạn kiến thức: B01-B09
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100