Giải bài trực tuyến

Hùng đang làm việc trong Công ty cao su X. Công ty có rừng cao su rất rộng, với những hàng cây cao su trồng cách đều thẳng tắp. Theo định kỳ, người ta thường phải chặt hạ cả hàng cây cao su đã hết hạn khai thác để trồng thay thế bằng hàng cây mới. Hùng phát hiện ra một bài toán tin học liên quan đến vấn đề này: Một nhóm công nhân được giao nhiệm vụ chặt hạ hàng cây gồm N cây được trồng dọc theo một đường thẳng với khoảng cách cố định giữa hai cây liên tiếp. Nếu các công nhân cưa đổ một cây, họ có thể cho nó đổ về phía bên trái hoặc bên phải dọc theo hàng cây. Một cây khi đổ có thể lật đổ cây khác bị nó rơi vào và có thể làm đổ nhiều cây khác, theo hiệu ứng lan truyền domino. Sau khi khảo sát kỹ, Hùng đã mô tả được hiệu ứng lan truyền domino như sau: Giả sử các cây trên hàng cây được đánh số từ 1 đến N, từ trái qua phải và chiều cao của cây i là h_i (1 <= i <= N)

• Nếu cây i đổ về bên trái thì tất cả các cây j với i – h_i < j < i cũng sẽ đổ;
• Nếu cây i đổ về bên phải thì tất cả các cây j với i < j < i + h_i cũng sẽ đổ;
• Mỗi cây chỉ đổ một lần về bên trái hoặc bên phải.

Do đó bài toán đặt ra đối với Hùng là: Xác định số lượng nhỏ nhất các cây mà các công nhân cần cưa đổ đảm bảo hạ đổ toàn bộ hàng cây.

Yêu cầu: Giúp Hùng giải quyết bài toán đặt ra.

Dữ liệu:

• Dòng đầu tiên ghi số nguyên dương N;
• Dòng thứ hai chứa N số nguyên dương h₁, h₂, …, h_n được ghi cách nhau bởi dấu cách, mỗi số không vượt quá 10⁶.

Kết quả:

• Dòng đầu tiên ghi số nguyên dương k là số lượng cây mà các công nhân cần cưa đổ;
• Dòng thứ hai ghi dãy số nguyên c₁, c₂, …, c_k trong đó |c_j| (1 <= j <= k) là dãy chỉ số của các cây theo thứ tự các công nhân phải lần lượt cưa đổ, c_j là số dương nếu cây cần cho đổ về bên phải và là số âm nếu cây cần cho đổ về bên trái. Nếu có nhiều cách thì chỉ cần đưa ra một cách tùy ý.

Ví dụ:

Chú ý: Còn một cách đốn cây khác: Cưa hai cây 1 và 2 và đều cho đổ về bên phải.

Ràng buộc:

• Có 40% số test ứng với 40% số điểm của bài có 1 <= N <= 10000.
• Có 40% số test khác ứng với 40% số điểm của bài có 1 <= N <= 100000.
• Có 20% số test còn lại ứng với 20% số điểm của bài có 1 <= N <= 4000000.