CSES - Aalto Competitive Programming 2024 - wk1 - Wed - Aquarium
  • Time limit: 2.00 s
  • Memory limit: 512 MB

Amy bought a unique aquarium at a flea market and she asked you to help her with pouring the water in.

The aquarium consists of nn hollow columns of heights h1,h2,hnh_1, h_2, … h_n that are glued together.
So for example an aquarium consisting of 1010 columns with heights (9,5,4,7,3,6,5,2,4,8)(9, 5, 4, 7, 3, 6, 5, 2, 4, 8) will look like this:

Now she asks you to start pouring VV liters of water in column qq (1-based indexing), but you are afraid of overfilling, so you agreed to write her a program that will help her and you as well. The program should tell you how high the water level will be when measured from the bottom of column qq after you are done pouring VV liters of water in it.

Note that the water may overflow from one column to adjacent columns (with the same rate to left and right columns) and the water might also spill out of the aquarium.

Input:

The first line contains an integer nn which is the number of columns of the aquarium.

The second line contains h1,h2,hnh_1, h_2, … h_n which are heights of columns (floating point numbers)

The third line contains two integers qq and VV where qq is the index of column where to pour water and VV number of liters to pour.

Output:

WW water level when measured from the bottom of column qq after done pouring VV liters of water in column qq.

Note that your solution is going to be accepted if |your answer - real answer| is less than 0.01.

Constraints

  • 0<n<1040 < n < 10^4
  • 1.0<hi<1061.0 < h_i < 10^6
  • 1qn1 \leq q \leq n
  • 1.0<V<10121.0 < V < 10^{12}

Example 1

Input:

10
9 5 4 7 3 6 5 2 4 8
6 72

Output:

8

Example 2

Input:

10
9 7 5 3 1 2 4 6 8 10 
5 11

Output:

3.66667

For better understanding of example 1, look at following pictures:
After pouring 10 liter of water in the column 6, we will have the following state:

and after pouring two more liter:

In the end, after pouring all 72 liters of water, we will reach to the following state, and column 6 will have height 8: