데산트

오랜 세월 비토시아는 바이토시아를 정기적으로 습격해 자연 자원과 지적 자산을 빼앗아 왔다. 이번에는 바이토시아인이 교활한 비토시아 민족을 먼저 공격한다. 치밀하게 짜인 전략의 첫 단계는 비토바이타나 해변에 대한 상륙이다.

작전은 은밀하게 진행되어야 하므로, 정예 부대 바이토그롬의 대원 정확히 $k$명으로 구성된 분대를 해변으로 보낸다. 현재 부대에는 $n$명의 병사가 있으며, 1부터 $n$까지 번호가 붙어 있다. $i$번 병사의 근접 전투 수준은 $i$이고, 원거리 전투 수준은 $a_i$이다. 수열 $a_1, \ldots, a_n$은 1부터 $n$까지의 순열이다. 수준이 높을수록 그 분야에서 더 숙련된 병사이다.

잘 운영되는 특수 부대에서는 누구의 명령을 따르고 누구에게 명령할 수 있는지를 모두가 알아야 한다. 두 병사 $i$와 $j$가 모두 작전에 나가고 $i < j$이며 $a_i > a_j$이면, 둘 사이에 마찰이 생길 수 있다. 두 병사는 바이토그롬에서 누가 더 높은지를 두고 다투게 된다.

상륙을 위해 $k$명을 고를 때, 마찰이 생길 수 있는 쌍의 수가 최소가 되도록 골라야 한다. 그 최소 쌍의 수를 구하라. 또한 이 최소를 달성하는 $k$명 분대를 고르는 방법의 수를 구하라. $k$를 1부터 $n$까지 바꿔 가며 각각에 대해 답하라.

첫 줄에 정수 $n$ ($1 \le n \le 40$)이 주어진다. 바이토그롬의 병사 수이다.

둘째 줄에 정수 $n$개 $a_1, \ldots, a_n$ ($1 \le a_i \le n$, $i \ne j$이면 $a_i \ne a_j$)이 주어진다. $a_i$는 $i$번 병사의 원거리 전투 수준이다.

$n$개의 줄을 출력한다. $k$번째 줄에는 정확히 $k$명을 보낼 때 마찰이 생길 수 있는 쌍의 최소 개수와, 그 최소를 달성하는 방법의 수를 공백으로 구분해 출력한다.

$k=1$이면 마찰이 생길 쌍이 없고, 그 병사는 5가지 방법으로 고를 수 있다.

$k=2$이면 마찰이 생기지 않도록 (2, 4), (3, 4), (3, 5) 중 하나의 쌍을 골라야 한다.

$k=3$이면 (2, 3, 4) 또는 (3, 4, 5)를 보내 마찰이 생길 쌍을 하나로 줄일 수 있다.

$k=4$이면 첫 번째 병사를 제외한 나머지를 모두 보내는 것이 최선이다. 첫 번째 병사는 번호 때문에 근접 전투가 가장 낮지만, 원거리 전투 수준 $a_1 = 5$가 가장 높아서 다른 모든 병사와 마찰을 일으킬 수 있다.

$k=5$이면 일곱 쌍이 마찰을 일으킨다.