Đốn cây

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\le i\le 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ẽ đổ (về bên trái);
• 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ẽ đổ (về bên phải);
• 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 vào

• 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_1,h_2,\dots ,h_n$ được ghi cách nhau bởi dấu cách, mỗi số không vượt quá ${10}^6$.

Dữ liệu ra

• 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_1,c_2,\dots ,c_k$, trong đó $|c_j|$ $(1\le j\le 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.

Không được cưa một cây đã đổ. Nếu có nhiều cách thì chỉ cần đưa ra một cách tùy ý.

Ràng buộc

• $1\le n\le 4·{10}^6$;
• $1\le h_i\le {10}^6$.

Subtasks

• Subtask 1 ($40\%$ số test, $40\%$ số điểm): $1\le n\le {10}^4$;
• Subtask 2 ($40\%$ số test, $40\%$ số điểm): $1\le n\le {10}^5$;
• Subtask 3 ($20\%$ số test, $20\%$ số điểm): $1\le n\le 4·{10}^6$.

Ví dụ