balba

// Bogdan Iordache
// 100 de puncte
// O(N*100)
#include <bits/stdc++.h>
using namespace std;

bool is_better(const vector<int>& candidate, const vector<int>& curr) {
    if (candidate.size() > curr.size()) return true;
    if (candidate.size() < curr.size()) return false;
    for (int i = 0; i < (int)curr.size(); ++i)
        if (curr[i] < candidate[i]) return true;
        else if (curr[i] > candidate[i]) return false;
    return false;
}

int main() {
    ifstream cin("balba.in");
    ofstream cout("balba.out");

    int C, N;
    cin >> C >> N;
    assert(1 <= C && C <= 2);
    assert(1 <= N && N <= 100000);

    vector<int> digits(N);
    for (int i = 0; i < N; ++i) {
        cin >> digits[i];
        assert(0 <= digits[i] && digits[i] <= 9);
    }

    string str;
    assert(!(cin >> str));

    if (C == 1) {
        int nr_seg = 1;
        int nr_seg_2 = 0;
        int curr_len = 1;

        for (int i = 1; i < N; ++i) {
            if (digits[i] == digits[i - 1]) {
                curr_len++;
            } else {
                nr_seg++;
                if (curr_len > 1) nr_seg_2++;
                curr_len = 1;
            }
        }
        if (curr_len > 1) nr_seg_2++;

        cout << nr_seg << '\n' << nr_seg_2;
    } else {
        vector<int> freq(10);
        for (int it : digits) freq[it]++;

        vector<int> sol = vector<int>(), candidate = vector<int>(),
                    aux = vector<int>();
        sol.reserve(N);
        candidate.reserve(N);
        aux.reserve(N);
        bool is_first, repeated;
        for (int repeat = -1; repeat <= 9; ++repeat) {
            for (int center = -1; center <= 9; ++center) {
                if (repeat == 9 && center == 9) {
                    center = 9;
                }
                if (center != -1) {
                    if (freq[center] == 0) continue;
                    freq[center]--;
                }
                if (repeat != -1) {
                    if (freq[repeat] < 3) {
                        if (center != -1) freq[center]++;
                        continue;
                    }
                    freq[repeat]--;
                }

                is_first = true;
                for (int i = 9; i >= 0; --i) {
                    if (freq[i] / 2 == 0) continue;
                    if (i == 0 && is_first) break;
                    is_first = false;
                    for (int j = 0; j < freq[i] / 2; ++j) aux.push_back(i);
                }

                repeated = false;
                for (int it : aux) {
                    if (it == repeat && !repeated) {
                        candidate.push_back(it);
                        repeated = true;
                    }
                    candidate.push_back(it);
                }
                if (center != -1) candidate.push_back(center);
                reverse(aux.begin(), aux.end());
                for (int it : aux) candidate.push_back(it);

                if (is_better(candidate, sol)) sol = candidate;

                candidate.clear();
                reverse(aux.begin(), aux.end());
                for (int it : aux) candidate.push_back(it);
                if (center != -1) candidate.push_back(center);
                reverse(aux.begin(), aux.end());
                repeated = false;
                for (int it : aux) {
                    if (it == repeat && !repeated) {
                        candidate.push_back(it);
                        repeated = true;
                    }
                    candidate.push_back(it);
                }

                if (is_better(candidate, sol)) sol = candidate;

                if (repeat != -1) freq[repeat]++;
                if (center != -1) freq[center]++;
                aux.clear();
                candidate.clear();
            }
        }

        for (auto it : sol) cout << it;
    }
    string s;
   assert(!(cin >> s));
    return 0;
}