Dr. Matrix has recently been working on permutations. He discovered that for a given permutation of size $n$, denoted as $P = (a_0, a_1, \dots, a_{n-1})$ (where for each $i$, $0 \le a_i \le n-1$), we can immediately calculate its "order number" $o(P)$. "Order number" is yet another new term from Dr. Matrix's boring discoveries, which he defines as $o(P) = \sum_{i=0}^{n-1} \delta_i$, where $\delta_i = \begin{cases} 1 & \text{if } a_i = i \\ 0 & \text{if } a_i \neq i \end{cases}$. To study order numbers thoroughly, Dr. Matrix selected all permutations of length $n$ that have the same order number as $P$ to form an "order equivalence set," and carefully arranged them in lexicographical order as $\{P_0, P_1, \dots, P_m\}$. Thus, a permutation can be described by its order number and its position within its order equivalence set. Note: Due to the doctor's peculiar nature, the position in the order equivalence set is always counted starting from 0.

One day, a fire broke out at the doctor's house (which, in fact, happens often). Some of the papers in the doctor's research manuscripts were charred. Afterward, he urgently needed to know the order number and the position within the order equivalence set for certain permutations. As the doctor's only assistant, you have taken on the task.

Input

The first line of the file contains a single integer $n$ ($1 \le n \le 64$), representing the length of the given permutation. The second line contains $n$ integers, representing the permutation in sequence. Note that the elements of the permutation range from $0$ to $n-1$.

Output

Output a single line containing two integers. The first integer represents the order number of the given permutation, and the second integer represents its position within its order equivalence set.

Examples

Input 1

4
2 0 3 1

Output 1

0 3

Input 2

4
0 1 3 2

Output 2

2 0

Constraints

For 40% of the data, $n \le 10$.

For 100% of the data, $n \le 64$.