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.