Untitled

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include "assert.h"
#include <set>
#include <iomanip>
#include <map>
#include <time.h>
using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair

const int N = 500050; //change!!!
const int MOD = 998244353;
const ll INF = 1e18;

int n, m, x;
int p[N];
vector <int> parent(N);
vector <int> sz(N);
int p1[N];
vector <pair<int, int> > oldsz;
vector<pair<int, int> > oldparent;

void make(int v) {
    parent[v] = v;
    sz[v] = 1;
}

int get(int v) {
    if (parent[v] == v) return v;
    oldparent.pb({v, parent[v]});
    return parent[v] = get(parent[v]);
}

void merge(int v, int u) {
    v = get(v);
    u = get(u);
    if (sz[v] < sz[u]) swap(v, u);
    oldparent.pb({u, parent[u]});
    parent[u] = v;
    oldsz.pb({v, sz[v]});
    sz[v] += sz[u];
}

bool used[N];

int calc() {
    for (int i = 1; i <= n; i++) used[i] = false;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            cnt++;
            int v = i;
            used[v] = 1;
            while (true) {
                v = p[v];
                if (used[v]) break;
                used[v] = 1;
            }
        }
    }
    return cnt;
}

bool check() {
    for (int i = 1; i < n; i++) {
        if (p[i] + p[i + 1] > x) return false;
    }
    return true;
}

int mn, mx;

bool tryadd(int a, int b, bool last) {
    if (a == b) return false;
    if (!last) {
        if (get(a) == get(b)) return false;
    }
    if (get(a) != get(b)) merge(a, b);
    return true;
}

bool solve(int l, int r, int numl, int numr) {
    if (l > r) {
        if (!check()) {
            assert(false);
            return false;
        }
        {
            //cout << 1 << "\n";
            //for (int i = 1; i <= n; i++) cout << p[i] << " ";
            //cout << "\n";
            return true;
        }
    }
    if (l == r) {
        if (l != numl) {
            p[l] = numl;
            return solve(l + 1, r - 1, numl + 1, numr - 1);
        }
    }
    else {
        vector <pair<int, int>> tmpsz, tmpparent;
        oldsz.clear();
        oldparent.clear();
        bool f1 = tryadd(l, numr, 0);
        bool f2 = tryadd(l + 1, numl, (l + 2 > r));
        tmpsz = oldsz;
        tmpparent = oldparent;
        bool res = 0;
        if (f1 && f2) {
            p[l] = numr;
            p[l + 1] = numl;
            res = solve(l + 2, r, numl + 1, numr - 1);
            if (res) {
                return true;
            }
            p[l] = 0;
            p[l + 1] = 0;
        }
        for (int i = (int)tmpsz.size() - 1; i >= 0; i--) {
            auto pp = tmpsz[i];
            sz[pp.first] = pp.second;
        }
        for (int i = (int)tmpparent.size() - 1; i >= 0; i--) {
            auto pp = tmpparent[i];
            parent[pp.first] = pp.second;
        }
        oldsz.clear();
        oldparent.clear();
        f1 = tryadd(r, numr, 0);
        f2 = tryadd(r - 1, numl, (l + 2 > r));
        tmpsz = oldsz;
        tmpparent = oldparent;
        if (f1 && f2) {
            p[r] = numr;
            p[r - 1] = numl;
            res = solve(l, r - 2, numl + 1, numr - 1);
            p[r] = 0;
            p[r - 1] = 0;
            if (res) return true;
        }
        for (int i = (int)tmpsz.size() - 1; i >= 0; i--) {
            auto pp = tmpsz[i];
            sz[pp.first] = pp.second;
        }
        for (int i = (int)tmpparent.size() - 1; i >= 0; i--) {
            auto pp = tmpparent[i];
            parent[pp.first] = pp.second;
        }
    }
    return false;
}

int main() {
    int t;
    //cin >> t;
    t = 199999;
    double mxsec = 0;
    int mxtst = 0;
    int xx = 2;
    while (t--) {
        //cin >> n >> x;
        n = xx;
        x = n + 1;
        xx++;
        if (n == 7 && x == 8) {
            cout << 2 << "\n";
            cout << "7 1 5 3 4 2 6\n";
            continue;
        }
        if (n == 7) {
            cout << 1 << "\n";
            cout << "2 7 1 6 3 5 4\n";
            continue;
        }
        for (int i = 1; i <= n; i++) make(i);
        clock_t t1 = clock();
        if (!solve(1, n, 1, n)) {
            cout << "FAIL " << n << endl;
            return 0;
        }
        clock_t t2 = clock();
        double sec = (double)(t2 - t1) / CLOCKS_PER_SEC;
        if (sec > mxsec) {
            //cout << n << " " << sec << endl;
            mxsec = sec;
            mxtst = n;
        }
    }
    cout << mxsec << " " << mxtst << endl;
    return 0;
}