Background

Description

Agent Maria has been sent to city S to carry out a particularly dangerous mission. She must use the subway to complete her task; city S has only one subway line in operation, so it is not complicated.

The current time is $0$. Maria starts from station $1$ and must meet the spy at the last station exactly at time $T$. She knows a powerful organization is tracking her. If she stays at a station, she faces a high risk of being caught; hiding in a moving train is safer. Therefore, she decides to stay on moving trains as much as possible, and she can ride only along the line in either direction (forward or backward).

To arrive at the last station on time and safely, Maria needs a plan that minimizes the total time she waits at stations. You must write a program to find Maria’s minimal total waiting time. Of course, if she arrives at the terminal earlier than the required time, she can wait at the station for the contact; this waiting time must also be counted.

There are $n$ stations, numbered $1 \sim n$. Trains shuttle along the line: either from station $1$ to station $n$, or from station $n$ back to station $1$. The travel time between any two consecutive stations is fixed, dwell times can be ignored, and Maria is extremely fast, so she can board or alight instantly, even if two trains arrive simultaneously.

Output Format

For each dataset, print one line $\text{\texttt{Case Number }\textit{N}\texttt{:}}$ (where $N$ starts from $1$) followed by an integer denoting the minimal total waiting time, or the word $\verb!impossible!$ if Maria cannot accomplish the task.

See the sample output.

4
55
5 10 15
4
0 5 10 20
4
0 5 10 15
4
18
1 2 3
5
0 3 6 10 12
6
0 3 5 7 12 15
2
30
20
1
20
7
1 3 5 7 11 13 17
0

Case Number 1: 5
Case Number 2: 0
Case Number 3: impossible

Hint

Explanation for Sample 1:

She boards at minute $0$, gets off at station $3$, immediately takes the train that left at minute $0$ and departs at minute $15$ to go back, gets to station $2$, immediately takes the train that started at minute $20$ and departs at minute $25$ to the terminal, arrives at minute $50$, and then needs to wait $5$ minutes.

Translated by ChatGPT 5