1D Peg Solitaire with Restricted Placements

You are given a 1×N board (N is an odd number) with K cells colored red. Initially, a special peg (called the original peg) is placed in the left‐most cell (cell 1) and no other pegs are on the board. Before any moves are made, you are allowed to put additional pegs on any empty cell (except cell 1) arbitrarily – these are called pre‐placements. However, once the game starts, any additional peg can only be placed on a red cell.

The game is played as follows. A move consists of choosing a single peg (either the original peg or one of the pegs placed earlier) and making a jump move. In a jump move the chosen peg jumps over an adjacent peg and lands in the cell immediately beyond it; the peg that was jumped over is captured (removed from the board). Note that a jump move is only allowed if:

• The cell immediately adjacent in the chosen direction contains a peg.
• The landing cell (immediately beyond the jumped peg) exists and is empty.
• If the peg being jumped over is the original peg, the move is not allowed (i.e. the original peg must never be captured).

Your goal is to move the original peg from cell 1 to cell N. In doing so, answer the following two questions:

1. What is the minimum number of pegs that must be placed before the first move (i.e. pre‐placements) in order to achieve the goal?
2. Assuming you use the minimum number of pre‐placements, what is the minimum number of additional peg placements during the game that you must perform in order to achieve the goal?
</p>

Additional rules:

• Pegs can only be placed on an empty cell. This applies both before the moves start as well as during the game.
• During the game, you are only allowed to add a peg on a red cell.
• The original peg (in cell 1 initially) must never be captured.

Input format:

The first line contains two integers N and K, where N is the number of cells (N is odd) and K is the number of red cells. The second line contains K distinct integers which denote the positions (1-indexed) of the red cells. Note that valid positions for pre‐placements are from 2 to N-1.

Output format:

Output two integers separated by a space. The first integer is the minimum number of pre‐placements needed and the second integer is the minimum number of in‐game placements needed (when using the minimal number of pre‐placements) to move the original peg from cell 1 to cell N.

inputFormat

Input begins with a line containing two integers N and K. The next line contains K distinct integers – the positions of the red cells. For example:

5 1
3

outputFormat

Output two space‐separated integers: the minimum number of pre‐placements and, with that minimal pre‐placement, the minimum number of in‐game placements required to achieve the goal. For example:

2 0

sample

5 1
3

2 0

</p>