Cụm dân cư

View as PDF



Problem types
Points: 400 (p) Time limit: 1.0s Memory limit: 1023M Input: stdin Output: stdout

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]\).


Comments

There are no comments at the moment.