Problem Description

Given a sequence $(s_1, s_2, \cdots, s_n)$ of length $n$ and three numbers $a, b, c$, you need to find a pair $L, R$ that satisfies:

$$\sum\limits_{i=L}^R s_i > a(bR - cL), \quad 1 \le L \le R \le n$$

That is, the sum of terms from the $L$-th to the $R$-th in the sequence is greater than $a \cdot (b \cdot R - c \cdot L)$. Among all $L, R$ that satisfy the condition, find the maximum value of $R - L + 1$.

The testdata guarantees that such a pair $L$ and $R$ exists.

Input Format

The first line contains four integers $n, a, b, c$, separated by single spaces.

The second line contains $n$ integers $s_1, s_2, \cdots, s_n$, separated by single spaces.

Output Format

Output one line containing one integer, which is the answer.

4 1 5 6
1 2 3 4

3

Hint

For $60\%$ of the test cases, $n \le 5000$.
For all test cases, $1 \le n \le 3 \times 10^5$, $1 \le a, b, c \le 1000$, and $|s_i| \le 10^9$.

Translated by ChatGPT 5