#K78237. Minimum Balls to Win

    ID: 35042 Type: Default 1000ms 256MiB

Minimum Balls to Win

Minimum Balls to Win

You are given an integer n and a list of ball numbers. In this game, you win by drawing a set of balls that, when rearranged, form a sequence of n consecutive integers. Formally, a sequence a1, a2, ..., an is consecutive if it can be reordered so that for the sorted sequence b1, b2, ..., bn the following holds:

$$b_{i} - b_{1} = i - 1 \quad \text{for all } 1 \le i \le n. $$

Your task is to determine the minimum number of balls that must be drawn such that the drawn balls can be rearranged into a sequence of consecutive integers. If it is impossible to form such a consecutive sequence with the drawn balls, output impossible.

Note: The list of ball numbers may contain extra balls beyond the required n balls. However, only the smallest n balls (after sorting) are considered when checking for consecutiveness.

inputFormat

The input is read from standard input and consists of two lines:

  • The first line contains a single integer n which is the number of consecutive balls required to win.
  • The second line contains a space-separated list of integers representing the ball numbers (the number of balls given can be greater than or equal to n).

It is guaranteed that the list contains at least n numbers.

outputFormat

Print a single line to standard output. If it is possible to select n balls that can be rearranged into a sequence of consecutive integers, output the integer n (i.e. the minimum number of balls drawn). Otherwise, print impossible.

## sample
5
2 4 3 6 1 5
5