Leaking Dike

Long ago a boy named Petrus saved his village by holding his finger in a leaking dike all night, through the cold, until the villagers found him and repaired it. This time the dike is leaking again, but Petrus is no longer alive to save the village. The villagers would rather gather their belongings and flee. Because packing takes time, each of them wants to know how long it will be before their own house is completely under water.

Model the village as a row of two-dimensional buildings standing on the x-axis. The buildings are packed side by side; every building is 1 meter wide and has a flat roof, but the roofs may be at different heights. At the left end (the beginning of the village) stands the dike, which is at least 1 meter taller than every building. Water leaks over the top of the dike at a rate of 1 square meter per minute and flows into the village. At the right end, attached to the last building, there is a wall exactly as tall as the dike, so no water can escape.

The buildings are solid and water enters only from the dike on the left, so a building taller than the current water surface acts as a dam: water can reach the lower ground beyond such a building only after the near side has filled up to that building's roof and spilled over the top. A building is "1 meter under water" the moment the water surface directly above its roof reaches 1 meter above that roof.

Water starts leaking at time 0. For one particular building, compute how many minutes pass until that building is 1 meter under water.

The input contains several test cases. Each test case is given on three lines:

• The first line contains an integer $n$ ($1 \le n \le 10000$), the number of buildings.
• The second line contains $n$ space-separated non-negative integers, each at most $10000$; the $i$-th value is the height of the building that occupies the x-interval $[i-1, i]$.
• The third line contains the number of the building whose submersion time you must report. Buildings are numbered from the left, starting at $1$.

The dike is based at x-coordinate $0$ and starts leaking at time $0$. The input ends with a line containing a single $0$.

For each test case, print one line containing the number of minutes until the given building goes 1 meter under water. Because every height is an integer and water accumulates at 1 square meter per minute, this time is always a whole number.