Điểm đổi chiều của chuỗi đo

Bối cảnh

Một thiết bị ghi liên tục n mẫu đo. Để phát hiện những thời điểm hệ thống đổi xu hướng, kỹ sư quan tâm đến các "điểm đổi chiều": một vị trí i nằm giữa dãy được tính nếu nó là cực đại cục bộ nghiêm ngặt (a[i] > a[i-1] và a[i] > a[i+1]) hoặc cực tiểu cục bộ nghiêm ngặt (a[i] < a[i-1] và a[i] < a[i+1]). Các đoạn bằng nhau không tạo điểm đổi chiều.

Hệ thống cần biết tổng số điểm đổi chiều và vị trí đầu tiên để ưu tiên kiểm tra log. Bài toán yêu cầu duyệt bằng recursion. Mỗi tầng chỉ chịu trách nhiệm đánh giá một index i dựa trên ba phần tử lân cận rồi chuyển sang i+1. Khác bài đếm đơn giản, bạn phải đồng thời duy trì count và firstIndex, đồng thời xử lý đúng các dãy quá ngắn không có vị trí nội bộ. Bối cảnh này gần với dạng xử lý tín hiệu cơ bản trong bài thi: tiêu chí cục bộ rõ ràng nhưng dễ sai ở biên và trường hợp bằng nhau.

Yêu cầu

1. Đọc n và mảng.
2. Dùng recursion xét các index 1..n-2.
3. Đếm số cực đại/cực tiểu cục bộ nghiêm ngặt.
4. Ghi nhận index đầu tiên; nếu không có dùng -1.
5. In count firstIndex.

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

Phần quét các index 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ố nếu n>0.

Output

Một dòng count firstIndex.

Ràng buộc

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

Ví dụ 1

Input

7
1 3 2 4 3 5 4

Output

5 1

Giải thích

Ta xét các index 1 đến 5. Index 1 có 3>1 và 3>2 nên là cực đại; index 2 có 2<3 và 2<4 nên là cực tiểu. Tương tự các index 3,4,5 cũng lần lượt đổi chiều. Tổng cộng có 5 điểm, và điểm đầu tiên nằm tại index 1. Vì vậy output là 5 1.

Ví dụ 2

Input

5
1 2 3 4 5

Output

0 -1

Giải thích

Dãy 1 2 3 4 5 tăng đều. Ở mỗi index nội bộ, giá trị không đồng thời lớn hơn cả hai hàng xóm và cũng không nhỏ hơn cả hai. Bộ đếm không tăng lần nào, firstIndex giữ giá trị -1, nên output là 0 -1.

Thông tin học tập

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