CENTER Thuê máy

Bờm là một start-up tài năng trong lĩnh vực xử lý dữ liệu lớn. Cậu đã nghiên cứu khá sâu về nhu cầu các đối tác tiềm năng và ước tính được lợi nhuận có thể đạt được trong n tháng tới, lợi nhuận của tháng thứ i có thể đạt được là p_i.

Để đáp ứng yêu cầu xử lý dữ liệu cho khách hàng, Bờm cần phải thuê thêm trung tâm máy tính lớn để làm việc với chi phí thuê mỗi tháng là C. Tuy nhiên, trung tâm chỉ chấp nhận cho thuê một số tháng liên tiếp. Do đó, Bờm cần tính toán thời điểm thuê để chi phí thuê không được vượt quá lợi nhuận có thể đạt được trong giai đoạn phải thuê thêm trung tâm.

Yêu cầu: Cho dãy số nguyên p₁, p₂, …, p_n và số nguyên C. Hãy tìm số thời điểm thuê khác nhau để chi phí thuê không vượt quá lợi nhuận có thể đạt được. Hai thời điểm thuê được gọi là khác nhau nếu có thời gian bắt đầu hoặc kết thúc khác nhau.

Input

• Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 10⁶)
• Dòng thứ hai chứa dãy số nguyên p₁, p₂, …, p_n (0 ≤ p_i ≤ 10⁹)
• Dòng thứ ba chứa số nguyên C (0 ≤ C ≤ 10⁹)

Output: ghi một số nguyên là số thời điểm thuê trung tâm.

Input	Output	Giải thích
5 4 1 3 4 2 3	7	7 giai đoạn thuê khác nhau là [1 .. 1], [1 .. 4], [3 .. 3], [3 .. 4], [3 .. 5], [4 .. 4], [4 .. 5]