Kiểm tra dãy hình núi nghiêm ngặt

Bối cảnh

Một tuyến đo độ cao gồm n mốc được xem là một "hình núi nghiêm ngặt" nếu tồn tại đúng một đỉnh không nằm ở hai đầu: trước đỉnh, độ cao phải tăng nghiêm ngặt ở mọi bước; sau đỉnh, độ cao phải giảm nghiêm ngặt ở mọi bước. Hai mốc liên tiếp bằng nhau làm dãy không hợp lệ. Ví dụ 1 3 5 4 2 hợp lệ với đỉnh index 2, còn 1 2 3 4 không hợp lệ vì không có pha giảm.

Bạn phải kiểm tra bằng recursion. Một cách tự nhiên là mang theo trạng thái pha: ban đầu đang ở pha UP; khi lần đầu gặp bước giảm, chuyển sang DOWN và ghi nhận index đỉnh; kể từ đó bất kỳ bước tăng hoặc bằng nào đều làm bài toán thất bại. Cần xử lý riêng việc đỉnh không được ở đầu hay cuối và dãy phải thật sự có cả hai pha. Bài này nâng độ khó so với kiểm tra tăng nghiêm ngặt vì recursion phải quản lý một finite-state machine nhỏ thay vì chỉ trả boolean từ một phép so sánh.

Yêu cầu

1. Đọc n và mảng.
2. Dùng recursion duyệt các cặp kề.
3. Dãy phải có pha tăng rồi pha giảm, đều nghiêm ngặt.
4. Nếu hợp lệ in YES peakIndex, nếu không in NO.

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

Phần kiểm tra pha phải thực hiện bằng recursion.

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ố.

Output

YES peakIndex hoặc NO.

Ràng buộc

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

Ví dụ 1

Input

5
1 3 5 4 2

Output

YES 2

Giải thích

Các cặp 1<3 và 3<5 giữ dãy ở pha UP. Khi gặp 5>4, recursion chuyển sang pha DOWN và ghi đỉnh là index 2, giá trị 5. Các bước sau 4>2 tiếp tục giảm nghiêm ngặt; đến hết dãy, cả hai pha đều đã xuất hiện và đỉnh không ở biên. Vì vậy output là YES 2.

Ví dụ 2

Input

4
1 2 3 4

Output

NO

Giải thích

Dãy 1 2 3 4 tăng nghiêm ngặt đến hết nhưng chưa bao giờ có bước giảm để chuyển sang pha DOWN. Khi recursion đi hết n phần tử, điều kiện "đã có pha giảm" vẫn sai, nên đây không phải hình núi theo định nghĩa. Output phải là NO.

Thông tin học tập

• Module: M04
• Buổi: B14
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: recursion, static arrays, phase state, mountain sequence, strict monotonicity
• Giới hạn kiến thức: B01-B14
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100