Background

In the year XXXX, detective Xiao Ming received a secret message from the organization: there is a mysterious door somewhere in Y City. After arriving at the door, he found a line of text: “This door requires a password to unlock.” Xiao Ming searched around and finally found a note: “Now you are given $n$ numbers. Please find how many contiguous numbers among these $n$ numbers have an average greater than a given number $M$. Note: this number can be very large, so please output the result modulo $92084931$. The final result is the password to this door.” Xiao Ming pondered for a long time but still couldn’t find the answer, so he turned to you for help. Please solve this problem for him. Since Xiao Ming is in a hurry, he can wait at most $1$ second.

Problem Description

Given $n$ numbers, help Xiao Ming count how many contiguous subarrays have an average greater than a given number $M$, and output this count. Note: the number can be very large, so please output the result modulo $92084931$.

Input Format

Two lines.
The first line contains two numbers $n$ and $M$.
The second line contains $n$ numbers.

Output Format

One line with a single number, which is the answer modulo $92084931$.

4 3
1 5 4 2

5

4 4
5 2 7 3

6

Hint

Sample explanation:

1. For these $4$ numbers, the valid solutions are $\{5\},\{4\},\{5,4\},\{1,5,4\},\{5,4,2\}$, for a total of $5$ groups.
2. For these $4$ numbers, the valid solutions are $\{5\},\{7\},\{2,7\},\{7,3\},\{5,2,7\},\{5,2,7,3\}$, for a total of $6$ groups.

Constraints:

• For $10\%$ of the testdata, $1 < n \le 10$.
• For $30\%$ of the testdata, $1 < n \le 1000$.
• For $50\%$ of the testdata, $1 < n \le 30000$.
• For $100\%$ of the testdata, $1 < n \le 200000$, $1 < M \le 3000$, and each number is a positive integer not greater than $5000$.

Translated by ChatGPT 5