MIDD

Cho một dãy số $A$ gồm $N$ phần tử $A_1,A_2,\dots ,A_N$, ta định nghĩa trung vị của dãy $A$ như sau: gọi $B$ là dãy thu được sau khi sắp xếp $A$ theo thứ tự tăng dần. Khi đó phần tử thứ $\lfloor \frac{N+1}{2}\rfloor$ của dãy $B$ (đánh số từ $1$) được gọi là trung vị của dãy $A$. Như vậy với dãy có độ dài chẵn, trung vị là phần tử bên trái trong hai phần tử đứng giữa; chẳng hạn trung vị của dãy $(7,3)$ là $3$.

Yêu cầu: Cho dãy số $A$ gồm $N$ phần tử $A_1,A_2,\dots ,A_N$. Với mỗi cặp chỉ số $[l,r]$ sao cho $1\le l\le r\le N$, gọi $M_{(l,r)}$ là phần tử trung vị của dãy $A_l,A_{l+1},\dots ,A_r$. Hỏi có bao nhiêu cặp chỉ số $[l,r]$ mà có phần tử trung vị lớn hơn hoặc bằng một giá trị $S$ cho trước.

Dữ liệu vào

• Dòng đầu ghi hai số nguyên $N,S$ $(2\le N,S\le {10}^5)$.
• Dòng thứ hai ghi $N$ số nguyên của dãy ban đầu $A_1,A_2,\dots ,A_N$ $(|A_i|\le {10}^9)$.

Dữ liệu ra

In ra một số nguyên duy nhất là số đoạn $[l,r]$ có trung vị lớn hơn hoặc bằng $S$.

Ràng buộc

• $2\le N\le {10}^5$.
• $2\le S\le {10}^5$.
• $|A_i|\le {10}^9$.

Subtasks

• Subtask 1 ($30\%$ số test): $N\le 400$.
• Subtask 2 ($40\%$ số test): $400<N\le 5000$.
• Subtask 3 ($30\%$ số test): ${10}^4\le N\le {10}^5$.

Mỗi test có số điểm như nhau.

Ví dụ