#include "triangles.h"

#include <bits/stdc++.h>

using namespace std;

std::vector<std::vector<int> > solve(int n) {
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    vector<int> bigger = {0, 1, 2};
    for (int i = 3; i < n; i++) {
        vector<Triangle> left, right;
        left.emplace_back(bigger[0], bigger[1], i);
        left.emplace_back(bigger[1], bigger[2], i);
        left.emplace_back(bigger[2], bigger[0], i);
        right.emplace_back(bigger[0], bigger[1], bigger[2]);
        if (compare(left, right) == 0) continue;
        vector<int> res = bigger;
        for (int j = 0; j <= 2; j++) {
            vector<int> cur = {bigger[j], bigger[(j + 1) % 3], i};
            left.clear(), right.clear();
            left.emplace_back(res[0], res[1], res[2]);
            right.emplace_back(bigger[j], bigger[(j + 1) % 3], i);
            if (compare(left, right) == -1)
                res = cur;
        }
        bigger = res;
    }
    vector<vector<int> > ans;
    ans.emplace_back(bigger);
    return ans;
}
