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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;

int n;
int tree[50];

inline int lsb(int a)
{
    return a & (-a);
}

void add_val(int val, int p)
{
    while(p <= n)
    {
        tree[p] += val;
        p += lsb(p);
    }
}

int read_val(int p)
{
    int ans = 0;
    while(p > 0)
    {
        ans += tree[p];
        p -= lsb(p);
    }
    return ans;
}

pair<int, int> addPairs(pair<int, int> a, pair<int, int> b)
{
    if(a.first == b.first) return {a.first, a.second + b.second};
    return min(a, b);
}

vector<int> k;

pair<int, int> theEnd[50];

int sum = 0;
int numElems = 0;
void dp(int p = 0)
{
    if(p == n)
    {
        theEnd[numElems] = addPairs(theEnd[numElems], {sum, 1});
        return;
    }
    dp(p + 1);
    add_val(1, k[p]);
    sum += read_val(k[p] - 1);
    ++numElems;
    dp(p + 1);
    sum -= read_val(k[p] - 1);
    add_val(-1, k[p]);
    --numElems;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        int in;
        cin >> in;
        k.push_back(in);
        theEnd[i + 1] = {999999999, 0};
    }
    reverse(k.begin(), k.end());
    dp();
    for(int i = 1; i <= n; ++i)
    {
        cout << theEnd[i].first << ' ' << theEnd[i].second << '\n';
    }
    return 0;
}