#include <algorithm>
#include <set>
#include "legos.h"
using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

const int MAXN = 2e5 + 10;
long long a[MAXN], n;

set <long long> s;

void add(int i) {
    int j = i + 1;
    if (j > n) j = 1;

    if (a[i] > a[j]) {
        long long ans = a[i];
        s.insert((ans << 32) + i);
    }
}

void remove(int i) {
    long long ans = a[i];
    s.erase((ans << 32) + i);
}

pair <bool, vector <pair <int, int>>> solve(vector <int> v) {
    n = v.size();

    int total = 0;

    for (int i = 1; i <= n; i++) {
        a[i] = v[i - 1];
        total = gcd(total, a[i]);
    }

    if (total != 1) return {0, {}};

    set <long long> candidates;

    for (int i = 1; i <= n; i++) {
        add(i);
    }

    const int MASK = (1 << 31) - 1;

    vector <pair <int, int>> ans;

    while (s.size()) {
        long long t = *s.rbegin();
        int i = t & MASK;
        int j = i + 1;
        if (j > n) j = 1;
        int k = i - 1;
        if (k < 1) k = n;

        remove(i);
        remove(k);

        int cnt = (a[i] - 1) / a[j];

        a[i] -= cnt * a[j];
        ans.push_back({i - 1, cnt});

        add(k);
    }

    reverse(ans.begin(), ans.end());
    return {1, ans};
}