There are \(n\) equidistant antennas on a line, numbered from \(1\) to \(n\). Each antenna has a power rating, the power of the \(i\)-th antenna is \(p_i\).
The \(i\)-th and the \(j\)-th antenna can communicate directly if and only if their distance is at most the minimum of their powers, i.e., \(|i-j| \leq \min(p_i, p_j)\). Sending a message directly between two such antennas takes \(1\) second.
What is the minimum amount of time necessary to send a message from antenna \(a\) to antenna \(b\), possibly using other antennas as relays?
Output
For each test case, print the number of seconds needed to trasmit a message from \(a\) to \(b\). It can be shown that under the problem constraints, it is always possible to send such a message.
Note
In the first test case, we must send a message from antenna \(2\) to antenna \(9\). A sequence of communications requiring \(4\) seconds, which is the minimum possible amount of time, is the following:
- In \(1\) second we send the message from antenna \(2\) to antenna \(1\). This is possible since \(|2-1|\le \min(1, 4) = \min(p_2, p_1)\).
- In \(1\) second we send the message from antenna \(1\) to antenna \(5\). This is possible since \(|1-5|\le \min(4, 5) = \min(p_1, p_5)\).
- In \(1\) second we send the message from antenna \(5\) to antenna \(10\). This is possible since \(|5-10|\le \min(5, 5) = \min(p_5, p_{10})\).
- In \(1\) second we send the message from antenna \(10\) to antenna \(9\). This is possible since \(|10-9|\le \min(5, 1) = \min(p_{10}, p_9)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
10 2 9
4 1 1 1 5 1 1 1 1 5
1 1 1
1
3 1 3
3 3 1
|
4
0
2
|