1107 - Nông dân chụp ảnh

Tạo bởi: CLB Olympic Tin học HUTECH

Mô tả yêu cầu

Nông dân John xếp N con bò của mình (đánh số từ 1 đến N) thành một hàng ngang để đo chiều cao của chúng, kết quả đo được là con bò thứ i có chiều cao là h_i. Sau đó anh ta muốn chụp ảnh một số dãy con của hàng (mỗi dãy con gồm những con bò liên tiếp nhau) để mang đến dự thi cuộc thi nhiếp ảnh tại một hội chợ.

Cuộc thi này có một quy định là chỉ những bức ảnh có trung vị chiều cao của những con bò trong ảnh lớn hơn hoặc bằng K thì mới hợp lệ và được dự thi.

Số trung vị của một dãy số A_{1...X}X phần tử được ban tổ chức cuộc thi định nghĩa như sau:

  • Là số A_{X/2 +1} khi dãy A được sắp xếp không giảm nếu X chẵn.
  • Là số A_{(X+1)/2} khi dãy A được sắp xếp không giảm nếu X lẻ.

Bạn hãy đếm số bức ảnh hợp lệ mà nông dân John có thể chụp.

Dữ liệu vào

  • Dòng thứ nhất gồm hai số nguyên NK (1 \leq N \leq 10^5; 1 \leq K \leq 10^9)
  • Dòng thứ hai gồm N số nguyên h_1, h_2, h_3,..., h_N (1 \leq h_i \leq 10^9) lần lượt là chiều cao của từng con bò trong hàng.

Dữ liệu ra

In ra số bức ảnh mà nông dân John có thể chụp.

Ví dụ

Dữ liệu vào Sao chép
4 6
10 5 6 2
Dữ liệu ra Sao chép
7

Gợi ý/Hướng dẫn

Những dãy con hợp lệ là {10}, {6}, {10, 5}, {5, 6}, {6, 2}, {10, 5, 6}, {10, 5, 6, 2}.

Đăng nhập để làm bài
Thông tin
Giới hạn thời gian 1 giây
Giới hạn bộ nhớ 128 MB