P9637 "yyOI R1" youyou's Tampering (Hard Ver.)

**The Easy Version and the Hard Version differ only in the final required output; all other statements are identical.**

youyou is going to hold a contest. There are $n$ problems in this contest, and each problem has a difficulty value $v_i$. youyou gives a counting parameter $k(k\le n)$. He thinks that, for the $x(x \geq k)$-th problem, its solvability $a_x$ should be the sum of the difficulty values of the hardest $k$ problems among problems $1$ to $x$, after sorting their difficulty values in increasing order. Since problems $1$ to $k-1$ are too easy, youyou does not want to consider the solvability of these problems. Then the total solvability of this contest is the sum of solvability from problem $k$ to problem $n$, that is, the value of $\sum^{n}_{i=k}a_i$. He can tamper with the difficulty of problem $m$ and change it to any positive integer. Given that the total solvability must lie within the interval $[l,r]$, how many possible values can the total solvability take?

The first line contains five positive integers $n,m,k,l,r$. The second line contains $n$ integers, where the $i$-th integer $v_i$ is the difficulty value of the $i$-th problem.

Output one integer in a single line, indicating the number of possible values of the total solvability under the constraints.

### Sample Explanation #1 You can modify $v_1$, and $k=1$. When the first number is changed to $1$, the total difficulty is $1+2+2+2+2=9$. When the first number is changed to $2$, the total difficulty is $2+2+2+2+2=10$. Only these two values satisfy the requirement, i.e. the total difficulty equals $9$ or $10$. Therefore, the answer is $2$. ### Constraints This problem uses **Subtasks**. For each **Subtask**, you need to pass all test points to get the score for that part. | Subtask ID | $n$ | Score | | :-----------: | :-----------: | :-----------: | | $1$ | $\le10$ | $15$ | | $2$ | $\le10^3$ | $15$ | | $3$ | $\le10^5$ | $70$ | For $100\%$ of the testdata, $1\le k,t \le n \le 10^5$, $1 \le l \le r \le 10^{9}$, $1\le v_i\le10^9$. Translated by ChatGPT 5