For many years, Bitocja has been regularly invading Bajtocja, stealing its natural and intellectual resources. This time, it is the Bajtocjanie who will attack the treacherous nation of Bitocjanie. The first step of the meticulously planned strategy will be a landing on the beach of Bitobajtan.

The operation must be discreet, so a squad consisting of exactly $k$ members of the elite Bajtogrom unit will be sent to the beach. Currently, there are $n$ soldiers in the unit's ranks, denoted by consecutive natural numbers from $1$ to $n$. The soldier with index $i$ has mastered hand-to-hand combat at level $i$, and ranged combat at level $a_i$. The sequence $a_1, \dots, a_n$ forms a permutation of numbers from $1$ to $n$. The higher the level, the more advanced the soldier is in a given discipline.

As is well known, in a good special forces squad, everyone should know who to listen to and who they can command. If two soldiers with indices $i$ and $j$ are sent on a mission simultaneously, such that $i < j$ and $a_i > a_j$, a so-called "clash" may occur between them—a situation where they argue, trying to determine who is more important in the ranks of Bajtogrom.

When choosing $k$ soldiers for the landing, you must do so in a way that minimizes the number of pairs of soldiers between whom a clash may occur. Your task is to determine what this minimum possible number of pairs is. Additionally, your task is to determine how many ways there are to choose a squad of $k$ soldiers to achieve this minimum.

One more thing. It is not yet known exactly how many soldiers we want to send to the beach of Bitobajtan. Therefore, determine the two aforementioned numbers for every $k$ from $1$ to $n$.

Input

The first line of input contains a single integer $n$ ($1 \le n \le 40$), representing the number of soldiers in the ranks of Bajtogrom.

The second line contains $n$ integers $a_1, \dots, a_n$ ($1 \le a_i \le n$, $a_i \neq a_j$ for $i \neq j$), where $a_i$ describes the $i$-th soldier and denotes their level of advancement in ranged combat.

Output

The output should contain $n$ lines, each containing two integers.

The numbers in the $k$-th line should represent the minimum number of pairs of soldiers between whom a clash may occur if we want to send exactly $k$ soldiers on the landing, and the number of ways in which we can achieve this minimum.

Examples

Input 1

5
5 3 1 4 2

Output 1

0 5
0 3
1 2
3 1
7 1

Note

If we want to send only one soldier, there is obviously no one to have a clash with, and that soldier can be chosen in five ways.

If we want to send two soldiers, we must choose one of the pairs $(2, 4)$, $(3, 4)$, or $(3, 5)$ to ensure no clash occurs.

If we want to send three soldiers, one pair threatening a clash can be achieved by sending the squad $(2, 3, 4)$ or $(3, 4, 5)$.

If we want to send four soldiers, it is optimal to send everyone except the first one, who, besides being the worst in hand-to-hand combat (due to being the first), is also the best in ranged combat (due to $a_1 = 5$), which causes a risk of a clash with every other soldier.

If we want to send all five soldiers, as many as seven pairs threaten a clash.