Landing Raid

For many years Bitocja has regularly raided Bajtocja, stealing its natural and intellectual resources. This time the Bajtocjans will strike first against the treacherous Bitocjan people. The first step of a carefully planned strategy is a landing on the beach of Bitobajtan.

The operation must be discreet, so a squad of exactly $k$ members of the elite unit Bajtogrom will be sent to the beach. The unit currently has $n$ soldiers, numbered from 1 to $n$. Soldier $i$ has hand-to-hand combat level $i$ and ranged combat level $a_i$. The sequence $a_1, \ldots, a_n$ is a permutation of the numbers from 1 to $n$. A higher level means the soldier is more advanced in that discipline.

In a well-run special unit, everyone must know whom to obey and whom they may give orders to. If two soldiers $i$ and $j$ are both sent on the mission, with $i < j$ and $a_i > a_j$, friction may occur between them. They will quarrel over who outranks whom in Bajtogrom.

When choosing $k$ soldiers for the landing, the squad must be chosen so that the number of pairs that may cause friction is as small as possible. Find that minimum number of pairs. Also find the number of ways to choose a squad of $k$ soldiers that reaches this minimum. Do this for every $k$ from 1 to $n$.

The first line contains one integer $n$ ($1 \le n \le 40$), the number of soldiers in Bajtogrom.

The second line contains $n$ integers $a_1, \ldots, a_n$ ($1 \le a_i \le n$, $a_i \ne a_j$ for $i \ne j$), where $a_i$ is the ranged combat level of soldier $i$.

Print $n$ lines, each with two integers. On line $k$, print the minimum number of pairs that may cause friction when exactly $k$ soldiers are sent, followed by the number of ways to reach that minimum.

For $k=1$, no pair of soldiers can cause friction, and the single soldier can be chosen in 5 ways.

For $k=2$, one of the pairs (2, 4), (3, 4), or (3, 5) must be chosen, so that no friction occurs.

For $k=3$, sending (2, 3, 4) or (3, 4, 5) leaves only one pair that may cause friction.

For $k=4$, it is best to send everyone except the first soldier. The first soldier is the weakest in hand-to-hand combat because of his index, but has the highest ranged level, $a_1 = 5$, so he may cause friction with every other soldier.

For $k=5$, seven pairs may cause friction.