Background

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

Problem Description

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?

Input Format

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 Format

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

5 1 1 5 10
1 2 2 2 2

2

Hint

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.

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