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
81
82
83
84
85
86
87
88
// Author: Bartek Knapik

#include <cstdio>
#include <queue>

using namespace std;

int h[3009];
int m[3009];
int visited[3009];
int n, cnt, ans;

deque<int> cycle;
deque<int> buffer[2];

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &h[i]);
        m[h[i]] = 1;
    }

    cnt = 0;

    for (int i = 0; i < 3009; ++i)
    {
        if (m[i] == 0) continue;
        m[i] += cnt;
        cnt++;
    }

    for (int i = 1; i <= n; ++i)
        h[i] = m[h[i]];

    ans = 0;

    for (int c = 0; c < 2; ++c)
    {
        for (int i = 1; i <= n; ++i)
        {
            if (visited[i] == c + 1 || i == h[i]) continue;

            int cur, next, start;
            cur = i;
            cycle.clear();
            cycle.push_back(cur);
            while (true)
            {
                next = h[cur];
                if (next == i) break;
                visited[next] = c + 1;
                cycle.push_back(next);
                cur = next;
            }

            if (cycle.size() & 1)
                cycle.pop_back();

            while (cycle.size())
            {
                int pos1 = cycle.front(); cycle.pop_front();
                int pos2 = cycle.back(); cycle.pop_back();
                buffer[c].push_back(pos2);
                buffer[c].push_front(pos1);
                int tmp = h[pos1];
                h[pos1] = h[pos2];
                h[pos2] = tmp;
            }
        }
        if (buffer[c].size()) ans++;
        else break;
    }

    printf("%d\n", ans);

    for (int c = 0; c < ans; ++c)
    {
        printf("%ld\n", buffer[c].size());
        for (int j = 0; j < buffer[c].size(); ++j)
            printf("%d ", buffer[c][j]);
        printf("\n");
    }

    return 0;
}