1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
//Krzysztof Boryczka
#pragma GCC optimize "O3"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;

#define FOR(i, b, e) for(int i=b; i<=e; i++)
#define FORD(i, b, e) for(int i=b; i>=e; i--)
#define SIZE(x) ((int)x.size())
#define pb push_back
#define st first
#define nd second
#define sp ' '
#define ent '\n'

const int N=45;

ii ans[N];
vi G[N];
int t[N];
int n, ilosc, cols;
bool jest[N];

void generuj(int k){
	if(k==n+1){
		if(cols < ans[ilosc].st) ans[ilosc]={cols, 0};
		if(cols == ans[ilosc].st) ans[ilosc].nd++;
		return;
	}
	generuj(k+1);
	jest[k]=1;
	ilosc++;
	for(auto &x: G[k]) if(jest[x]) cols++;
	generuj(k+1);
	jest[k]=0;
	ilosc--;
	for(auto &x: G[k]) if(jest[x]) cols--;
}

void solve(){
	cin>>n;
	FOR(i, 1, n) cin>>t[i];
	FOR(i, 1, n) FOR(j, i+1, n) if(t[i]>t[j]) G[i].pb(j), G[j].pb(i);
	FOR(i, 1, n) ans[i]={inf, 0};
	generuj(1);
	FOR(i, 1, n) cout<<ans[i].st<<sp<<ans[i].nd<<ent;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	// int tt; cin>>tt;
	// FOR(te, 1, tt)
	solve();
	return 0;
}