습격

과거 여러 해 동안 비토시아는 바이토시아를 침략해 자연 자원과 지적 재산을 빼앗아 왔다. 그러나 이번에는 바이토시아가 교활한 나라 비토시아를 침공한다. 이 신중하게 계획된 침공의 첫 단계는 비토비티아 해변에 대한 습격이다.

침공은 눈에 띄지 않아야 하므로, 바이트포스 정예군의 병사 $k$명이 이 해변으로 가라는 명령을 받는다. 현재 바이트포스에는 1부터 $n$까지 연속된 번호가 붙은 병사 $n$명이 있다. $i$번 병사의 근접 전투 기술 수준은 $i$이고, 원거리 전투 기술 수준은 $a_i$이다. 수열 $a_1, \ldots, a_n$은 1부터 $n$까지의 수로 이루어진 순열이다. 기술 수준이 높을수록 해당 분야에서 더 뛰어난 병사이다.

잘 짜인 부대에서는 누가 누구에게 명령을 내리고 누구의 명령을 따라야 하는지 모두가 알아야 한다. 선발된 병사 중 번호가 $i$, $j$인 두 명이 $i < j$이고 $a_i > a_j$를 만족하면, 둘은 누가 더 중요한지를 두고 다툴 가능성이 크다. 이런 쌍을 나쁜 쌍이라고 부른다.

이런 다툼을 막기 위해 나쁜 쌍의 수를 최소화하려 한다. 아직 몇 명을 보낼지는 정해지지 않았다. 1부터 $n$까지의 각 $k$에 대해, $n$명 중 정확히 $k$명을 고를 때 얻을 수 있는 나쁜 쌍의 최소 개수와, 그 최소 개수를 달성하는 방법의 수를 구하라.

첫 줄에 바이트포스의 병사 수 $n$이 주어진다 ($1 \leq n \leq 40$). 둘째 줄에는 정수 $a_1, \ldots, a_n$이 주어진다 ($1 \leq a_i \leq n$, $i \neq j$이면 $a_i \neq a_j$).

$n$개의 줄을 출력한다. $k$번째 줄에는 병사 $k$명을 보낼 때 다툴 수 있는 쌍의 최소 개수와, 그 최소 개수를 달성하는 방법의 수를 출력한다.

병사를 한 명만 보내면 다툼이 있을 수 없으므로 5가지 방법으로 할 수 있다.

두 명을 보내려면 다툼이 없도록 $(2, 4)$, $(3, 4)$, $(3, 5)$ 중 한 쌍을 골라야 한다.

세 명을 보내면 나쁜 쌍의 최소 개수는 1이며, $(2, 3, 4)$ 또는 $(3, 4, 5)$를 골라 이를 달성한다.

네 명을 보내려면 근접 전투에서 가장 약한 첫 번째 병사를 제외한 나머지를 고른다. 그는 근접 전투에서는 가장 약하지만 원거리 전투에서는 가장 뛰어나다($a_1=5$). 따라서 다른 모든 병사와 다툼을 일으킬 수 있다.

다섯 명을 모두 보내면 나쁜 쌍이 7개가 된다.