#include <algorithm> #include <iostream> #include <tuple> #include <vector> using namespace std; using i64 = long long; struct Solution { vector<tuple<int, int, int>> ans; vector<int> perm, pos; void swap(int i, int j, int k) { if (perm[i] > perm[k]) { std::swap(pos[perm[i]], pos[perm[j]]); std::swap(perm[i], perm[j]); } else { std::swap(pos[perm[j]], pos[perm[k]]); std::swap(perm[j], perm[k]); } } void add_ans(int i, int j, int k) { ans.emplace_back(i, j, k); swap(i, j, k); } void print(int lim) { if ((int)ans.size() > lim) { cout << "-1\n"; return; } cout << ans.size() << '\n'; for (const auto& op : ans) cout << get<0>(op) << ' ' << get<1>(op) << ' ' << get<2>(op) << '\n'; } // Case 1: n <= 3 void case_1(int n, int lim) { if (n == 1) cout << "0\n"; else if (n == 2) cout << (perm[1] < perm[2] ? "0\n" : "-1\n"); else if (n == 3) { for (int i = 0; i <= lim && !is_sorted(perm.begin() + 1, perm.end()); ++i) add_ans(1, 2, 3); print(lim); } } // Case 2: pos[1] == n void case_2() { cout << "-1\n"; } // Case 3: pos[1] == 1 void case_3(int n) { for (int i = 2; i <= n; ++i) { if (perm[i] != i) add_ans(1, min(i, pos[i]), max(pos[i], i)); } } // Case 4: (∃pos[1] < i <= n) perm[i] < perm[1] void case_4(int i, int n) { add_ans(1, pos[1], i); case_3(n); } // Case 5: perm[1] >= 3 void case_5(int n) { int i; for (i = 2; i < pos[1]; ++i) { if (perm[i] < perm[1]) break; } add_ans(1, i, n); case_4(n, n); } // Case 6: perm[1] == 2, perm[2] == 1, (∀3 <= i <= n) perm[i] == i void case_6(int n, int lim) { if (n == 4 && lim == 4) cout << "-1\n"; else cout << "5\n1 2 3\n1 2 3\n1 2 4\n1 3 4\n1 2 4\n"; } // Case 7: perm[1] == 2, perm[2] == 1 void case_7(int n) { int i; for (i = 3; i < n; ++i) { if (perm[i] > perm[i + 1]) break; } add_ans(1, 2, i); add_ans(1, 2, i); add_ans(1, i, i + 1); case_3(n); } // Case 8: perm[1] == 2 void case_8(int n) { if (pos[n] == 2) { add_ans(1, 2, pos[1]); add_ans(1, pos[1], n); } else { add_ans(1, 2, pos[n]); add_ans(1, 2, pos[1]); add_ans(1, pos[1], n); } case_3(n); } void solve() { int n, l; cin >> n >> l; perm.resize(n + 1); pos.resize(n + 1); for (int i = 1; i <= n; ++i) { cin >> perm[i]; pos[perm[i]] = i; } if (n <= 3) { case_1(n, l); return; } else if (pos[1] == n) { case_2(); return; } else if (pos[1] == 1) { case_3(n); print(l); return; } int i; for (i = pos[1] + 1; i <= n; ++i) { if (perm[i] < perm[1]) break; } if (i <= n) case_4(i, n); else if (perm[1] >= 3) case_5(n); else if (perm[1] == 2 && perm[2] == 1) { if (is_sorted(perm.begin() + 3, perm.end())) { case_6(n, l); return; } else case_7(n); } else if (perm[1] == 2) case_8(n); print(l); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t; cin >> t; while (t-- > 0) Solution().solve(); return 0; }