KTLT19. Cây sồi

KTLT19. Cây sồi
Từ cổng vào đến tòa chính của Bộ Quốc phòng có trồng một hàng n cây sồi (2 ≤ n ≤ 200). Các cây được đánh số từ 1đến n từ trái sang phải.
Để chuẩn bị đón Tổng tham mưu trưởng đến nhậm chức Bộ trưởng ra lệnh chặt bớt một số cây để dãy các cây còn lại thể hiện sắc nét hơn tính kỷ luật của một tổ chức quân sự. Chỉ thị nội bộ chỉ cho phép chặt một cây trong hai trường hợp:
• Cây sát ngay bên phải và cây sát ngay bên trái thực sự thấp hơn cây này,
• Cây sát ngay bên phải và cây sát ngay bên trái thực sự cao hơn cây này.
Như vậy, theo chỉ thị cây bên trái nhất và cây bên phải nhất của hàng sẽ không bị chặt.
Bộ trưởng yêu cầu lên kế hoạch chặt để trong hàng cây còn lại, mỗi cây sẽ không thấp hơn tất cả các cây bên trái nó trong hàng. Là một người yêu thiên nhiên, Bộ trưởng yêu cầu phải tìm cách chặt ít cây nhất.

Yêu cầu: Cho n và độ cao hi của cây thứ i (1 ≤ hi ≤ 1 000, i =1 ÷ n). Hãy xác định xem có thể chặt để tạo ra dãy cây như mong muốn hay không, nếu có thì chỉ ra số cây và các cây cần chặt.
Dữ liệu: Vào từ file văn bản OAKS.INP:
• Dòng đầu tiên chứa số nguyên n,
• Dòng thứ 2 chứa các số h1, h2, . . ., hn.
Kết quả: Đưa ra file văn bản OAKS.OUT: Nếu không có phương án chặt thì đưa ra số -1, trong trường hợp ngược lại:
• Dòng đầu tiên đưa ra số nguyên k – số cây cần chặt,
• Mỗi dòng trong k dòng sau chứa một số nguyên xác định cây cần chặt.
Ví dụ:
OAKS.INP
5
3 2 4 8 5
OAKS.OUT

2
2
4