Alaska

Interview

Time limit1sMemory limit128 MB

Summary
Given charging station positions along a 1422-mile highway and a 200-mile range, decide whether the round trip Dawson Creek to Delta Junction and back is possible.
Level

Medium4 of 10

Topics
Greedy, Sorting, Simulation, Implementation
Solved
No attempts yet

Problem

The Alaska Highway is a 1422-mile road connecting Dawson Creek and Delta Junction.

Sanggeun wants to drive his electric car from Dawson Creek to Delta Junction and then back to Dawson Creek. On a single full charge the car can travel 200 miles. There is a charging station at Dawson Creek, and there are more stations along the highway. Given the positions of the charging stations, write a program that determines whether Sanggeun can complete this round trip.

Input

The input consists of several test cases. The first line of each test case contains the number of charging stations on the highway, nn, a positive integer; the station at Dawson Creek is counted in nn. Each of the next nn lines gives the position of one charging station, as its distance from Dawson Creek, which is at least 0 and at most 1422. No two charging stations are at the same position. The last line of the input contains 0, marking the end of the input.

Output

For each test case, print POSSIBLE on its own line if Sanggeun can drive from Dawson Creek to Delta Junction and back to Dawson Creek, and IMPOSSIBLE otherwise.

Examples3

  1. Example 1

    Input
    2
    0
    900
    8
    1400
    1200
    1000
    800
    600
    400
    200
    0
    0
    
    Expected output
    IMPOSSIBLE
    POSSIBLE
    
  2. Example 2

    Input
    2
    0
    900
    8
    1400
    1200
    1000
    800
    600
    400
    200
    0
    1
    0
    0
    
    Expected output
    IMPOSSIBLE
    POSSIBLE
    IMPOSSIBLE
    
  3. Example 3

    Input
    9
    0
    200
    400
    600
    800
    1000
    1200
    1400
    1422
    0
    
    Expected output
    POSSIBLE