Giá trung bình

Để có thể đưa ra những quyết định mua vào, bán ra hợp lý của cổ phiếu thì nhà đầu tư chứng khoán cần phân tích tình hình thị trường thật kỹ lưỡng. Một trong những yếu tố quan trọng được nhiều nhà đầu tư quan tâm là giá bán trung bình của một cổ phiếu so với một mức giá tham chiếu.

Yêu cầu: Xét giá bán của một cổ phiếu trong $N$ phiên giao dịch và một mức giá tham chiếu $P$. Hãy viết chương trình cho biết có bao nhiêu phiên giao dịch liên tiếp trong $N$ phiên trên có giá bán trung bình lớn hơn hoặc bằng giá tham chiếu $P$. Cụ thể là nếu đánh số các phiên giao dịch từ $1$ đến $N$ thì có bao nhiêu cặp chỉ số $(L,R)$ ($1\le L\le R\le N$) để giá trung bình của các cổ phiếu trong phiên giao dịch từ $L$ đến $R$, tức là ${\displaystyle \frac{G_L+G_{L+1}+\dots +G_R}{R-L+1}}$, là lớn hơn hoặc bằng giá $P$.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên $N$ ($1\le N\le {10}^6$).
• Dòng thứ hai chứa $N$ số nguyên $G_1,G_2,\dots ,G_N$ ($0\le G_i\le {10}^9$) lần lượt cho biết giá bán của cổ phiếu trong $N$ phiên giao dịch.
• Dòng thứ ba chứa số nguyên $P$ ($0\le P\le {10}^9$) là mức giá tham chiếu.

Dữ liệu ra

In ra một số nguyên là số phiên giao dịch liên tiếp (số cặp $(L,R)$) trong $N$ phiên được xét có giá bán trung bình lớn hơn hay bằng giá tham chiếu $P$.

Ràng buộc

• $1\le N\le {10}^6$.
• $0\le G_i\le {10}^9$.
• $0\le P\le {10}^9$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $N\le 1000$.
• Subtask 2 ($20\%$ số điểm): $1000<N\le {10}^4$.
• Subtask 3 ($50\%$ số điểm): $5·{10}^5<N\le {10}^6$.

Ví dụ