Knights
Memory limit: 32 MB
A knight attacks squares on the chess-board as is show in the following figure
(the knight on the square
attacks squares marked by a cross).
There is a chess-board of dimensions
, with
rows and
columns,
where
, and there is a set
of fields on the chess-board.
The rows are numbered from the top to the bottom with numbers from
to
,
the columns from the left to the right with numbers from
to
.
Knights can be put only on the squares from the set
and no two of them can attack each other.
We assume that in each column at most one field belongs to the set
.
Thus the set
may be described with a series:
,
where
.
If
then no field in the
-th column belongs to the set
,
else
is a number of a row of the only field in this column, which belongs to
.
Task
Write a program that:
- reads from the standard input the number of columns on the chess-board
and the description of the set
,
- computes the maximal number of knights
,
that may be put on the chess-board according to the given rules,
and
— the number of possible arrangements of
knights on this chess-board,
- writes the results to the standard output.
Input
In the first line of the standard input there is written one positive integer
,
.
This is the number of columns in the chess-board.
In each of the following
lines there is written one number form the set
.
These are the consecutive terms of the series describing the set
.
Output
In the standard output two integers
and
separated by a single space should be written.
Example
For the input data:
2
1
0
the correct result is:
4 2
Task author: Wojciech Rytter.