Cụm dân cư

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Small
Dạng bài
Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Vương quốc Ba Sao tươi đẹp, người dân hiền lành chăm chỉ làm ăn. Tại đây có \(N\) ngôi làng nằm dọc theo đường quốc lộ, mỗi ngôi làng đều dự trữ một lượng lương thực nhất định cho làng của mình. Làng thứ \(i\) có số lương thực dự trữ là \(a_i\). Các làng liên tiếp có thể kết nghĩa với nhau thành một cụm dân cư nếu có lượng lương thực trung bình cộng lớn hơn hoặc bằng \(P\).

Yêu cầu: Hãy xác định số cụm dân cư khác nhau có thể hình thành trong vương quốc

Input

  • Dòng đầu chứa số nguyên \(n\ (1 \le n \le 10^6)\)
  • Dòng hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n\ (1 \le a_i \le 10^9)\)
  • Dòng cuối chứa một số nguyên dương \(P\ (1 \le P \le 10^9)\).

Output

  • Ghi một số nguyên không âm duy nhất là kết quả tìm được.

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(K \le 10^2\).
  • Subtask \(2\) (\(40\%\) số điểm): \(K \le 10^5\);
  • Subtask \(3\) (\(40\%\) số điểm): \(K \le 10^9\).

Example

Test 1

Input 
3
1 3 2
2
Output 
5
Note

Giải thích: Trong ví dụ trên, có 5 dãy con liên tiếp thỏa mãn là: \([1, 2], [1,3], [2,2], [2,3], [3,3]\).

Bình luận