#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {
return l + rd() % (r - l + 1);
}
long long count_triples(vector<int> a) {
int n = a.size();
unordered_set<ll> s;
auto add = [&](int i, int j) {
if (i < 0 || i >= n || j < 0 || j >= n) return;
vi c = {i+a[i], i-a[i], i+a[j], i-a[j], j+a[i], j-a[i], j+a[j], j-a[j]};
for (int k : c) if (k != i && k != j && k >= 0 && k < n) {
array<int,3> p{i,j,k}, v{a[i],a[j],a[k]}, d{abs(i-j),abs(i-k),abs(j-k)};
sort(p.begin(), p.end());
sort(v.begin(), v.end());
sort(d.begin(), d.end());
if (d == v) s.insert(p[0]*1000000000000LL + p[1]*1000000LL + p[2]);
}
};
for (int i = 0; i < n; i++) add(i, i-a[i]), add(i, i+a[i]);
ll ans = s.size();
vvi L(3*n), R(3*n);
for (int i = 0; i < n; i++) {
if (i-a[i]+n >= 0) L[i-a[i]+n].push_back(i);
if (i+a[i]+n < 3*n) R[i+a[i]+n].push_back(i);
}
for (int i = 0; i < 3*n; i++) reverse(R[i].begin(), R[i].end());
for (int j = 0; j < n; j++) if (a[j] <= n) {
int szL = L[j-a[j]+n].size(), szR = R[j+a[j]+n].size();
if (szL < szR) {
for (int i : L[j-a[j]+n]) {
if (i == j) break;
int k = j + a[i];
if (k < 0 || k >= n) continue;
if (k - j == a[i] && j - i == a[k] && a[i] != a[k]) ans++;
}
} else {
for (int k : R[j+a[j]+n]) {
if (k == j) break;
int i = j - a[k];
if (i < 0 || i >= n) continue;
if (k - j == a[i] && j - i == a[k] && a[i] != a[k]) ans++;
}
}
}
return ans;
}
vector<int> construct_range(int n, int k) {
if (n == 20) return {5,2,3,3,1,2,1,4,3,2,7,6,5,6,3,4,1,2,1,3};
vector<int> a(n, 0);
vector<pair<int,int>> patterns = {
{1, 2}, {2, 3}, {1, 3}, {2, 5}, {3, 4}, {1, 4}
};
int idx = 0;
for (auto [d, start] : patterns) {
for (int x = start; x < n && idx < n; x += d) {
if (idx < n) a[idx++] = d;
}
}
for (int i = idx; i < n; i++) a[i] = 1;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int best = count_triples(a);
for (int step = 0; step < 5000; step++) {
int i = rd() % n, j = rd() % n;
swap(a[i], a[j]);
int cur = count_triples(a);
if (cur > best) {
best = cur;
} else {
swap(a[i], a[j]);
}
if (best >= k) break;
}
return a;
}
