Problem Background

NOIP2018 Junior Group T2

Problem Description

Xuanxuan and Kaikai are playing a game called "Dragon and Tiger Fight". The game board is a line segment with $n$ camps (numbered from 1 to $n$ from left to right), with each adjacent camp separated by 1 centimeter, making the board a line segment of length $n-1$ centimeters. The $i$-th camp contains $c_i$ engineers. The following figure 1 is an example for $n=6$:

Xuanxuan is on the left, representing the "Dragon"; Kaikai is on the right, representing the "Tiger". They use the $m$-th camp as the boundary, with the engineers on the left belonging to the Dragon faction, those on the right belonging to the Tiger faction, and the engineers in the $m$-th camp being undecided and not belonging to either side.

The power of a camp is calculated as the number of engineers in that camp multiplied by the distance of the camp from the $m$-th camp. The power of one side is defined as the sum of the powers of all camps belonging to that side.

The following figure 2 is an example for $n = 6, m = 4$, with red representing the Dragon side and yellow representing the Tiger side:

During the game, a sudden event occurs where $s_1$ engineers appear in the $p_1$-th camp. As a friend of Xuanxuan and Kaikai, you know that if the power difference between the Dragon and Tiger sides is too large, they will not want to continue playing. To keep the game going, you need to choose a camp $p_2$ and send all your $s_2$ engineers to that camp, aiming to minimize the power difference between the two sides.

Note: The engineers you send to a camp will belong to the same faction as the other engineers in that camp (if they are sent to the $m$-th camp, they do not belong to either faction).

Input Format

The first line of the input file contains a positive integer $n$, representing the number of camps.

The next line contains $n$ positive integers separated by spaces, where the $i$-th integer represents the initial number of engineers $c_i$ in the $i$-th camp.

The next line contains four positive integers separated by spaces, representing $m, p_1, s_1, s_2$ respectively.

Output Format

The output file contains one line with a positive integer, which is the camp number $p_2$ you choose. If there are multiple camp numbers that achieve the optimal result, output the smallest one.

Sample Input and Output

Sample Input #1

6
2 3 2 3 2 3
4 6 5 2

Sample Output #1

2

Sample Input #2

6
1 1 1 1 1 16
5 4 1 1

Sample Output #2

1

Notes

Sample 1 Explanation

Refer to Figure 2 in the problem description.
The Dragon's power is:
$$2 \times (4-1) + 3 \times (4-2) + 2 \times (4-3) = 14$$
The Tiger's power is:
$$2 \times (5-4) + (3 + 5) \times (6-4) = 18$$
When you send $s_2 = 2$ engineers to the $p_2 = 2$ camp, the Dragon's power becomes:
$$14 + 2 \times (4-2) = 18$$
At this point, both sides have equal power.

Sample 2 Explanation

The boundary is the $m = 5$ camp, with $s_1 = 1$ engineer appearing in the $p_1 = 4$ camp.
The Dragon's power is:
$$1 \times (5-1) + 1 \times (5-2) + 1 \times (5-3) + (1 + 1) \times (5-4) = 11$$
The Tiger's power is:
$$16 \times (6-5) = 16$$
When you send $s_2 = 1$ engineer to the $p_2 = 1$ camp, the Dragon's power becomes:
$$11 + 1 \times (5-1) = 15$$
This minimizes the power difference between the two sides.

Data Constraints

$1 < m < n$, $1 \le p_1 \le n$.
For 20% of the data, $n = 3, m = 2, c_i = 1, s_1, s_2 \le 100$.
For another 20% of the data, $n \le 10, p_1 = m, c_i = 1, s_1, s_2 \le 100$.
For 60% of the data, $n \le 100, c_i = 1, s_1, s_2 \le 100$.
For 80% of the data, $n \le 100, c_i, s_1, s_2 \le 100$.
For 100% of the data, $n \le 10^5, c_i, s_1, s_2 \le 10^9$.

见题面 Input 部分

见题面 Output 部分