G :: The Security Team

Time Limit: 1 Second    Memory Limit: 32768 KB

An important welcome ceremony of some political officials is going to be held and as the manager of the security team, you are going to put your n agents along the red carpet. The agents are numbered 1 through n and equipped with wireless monaural headsets. The authorizations of the headsets are configured such that agent #i can only talk to agents #i-1 and #i+1 (if they exist of course). In addition, the headset of agent #i has a wireless range r_i, and agents #i and #j can talk only if their distance does not exceed the minimum of r_i and r_j. Your number-one rule of security is that any two agents should always be able to communicate directly or through some intermediate agents.
The red carpet is laid on a straight line, and the longer the carpet is, the more magnificent the ceremony looks like. But, the length of the carpet is limited since there must always be an agent on each head of the carpet and the agents must be connected as your number-one rule of security states.
Everything was running well till your boss arrived at the rehearsal of the ceremony one day before the main event. Having a look on your agents, the boss said:

• "The current placement of the agents along the red carpet does not seem so graceful. Arrange them along the carpet in ascending order of their heights. And by the way, the distance of no two agents should be less than one meter."

Confused from the new orders of the boss, you figure out that there is no time to reconfigure the authorization of the agents' headsets, and the only way to apply the new orders while keeping your own connectivity rule, is to shorten the length of the red carpet. Given the wireless range of the headsets and the height ordering of the agents, your job is to find the maximum possible length of the red carpet that could be used in the ceremony.

 

Input

There are multiple test cases in the input. Each test case starts with a line containing the integer n (1 <= n <= 10⁴), followed by a line having n space-separated integers which lists the agents' numbers in ascending order of their heights (e.g. 3 1 2 indicates agent #3 is the shortest and agent #2 is the tallest). It is guaranteed that all numbers 1 through n appear exactly once in this line. The test case ends with a line containing n space-separated integers r₁ r₂ ... r_n where r_i (1 <= r_i <= 10⁵) is the wireless range of the headset of agent #i given in meters. The input ends with a line containing a single zero which should not be processed as a test case.

Output

For each test case, you should print the maximum possible length of the red carpet along which you can put your agents (with an agent on each end) and keep all the agents connected while obeying the rules of the boss. If it is not possible to satisfy all the requirements together, write "Impossible" instead (without quotation marks).

Sample Input

5
3 4 5 1 2
6 6 6 6 6
3
1 3 2
1 2 1
0

Sample Output

6
Impossible

Submit

Source: Tehran, Asia Region - Regional 2011