#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
long long count_triples(std::vector<int> a) {
const int n = (int)a.size();
unordered_set<ll> seen;
auto check = [&](int i, int j) -> void {
if (i < 0 || i >= n) return;
if (j < 0 || j >= n) return;
vi cand = {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 : cand) if (k != i && k != j && k < n && k >= 0) {
array<int, 3> id{i, j, k}, v{a[i], a[j], a[k]}, d{abs(i-j), abs(i-k), abs(j-k)};
sort(id.begin(), id.end());
sort(v.begin(), v.end());
sort(d.begin(), d.end());
if (d == v) seen.insert(id[0]*(ll)1e12+id[1]*(ll)1e6+(ll)id[2]);
}
};
for (int i = 0; i < n; i++) check(i, i-a[i]), check(i, i+a[i]);
ll ans = seen.size();
vvi pk(3*n), nk(3*n);
for (int i = 0; i < n; i++) {
if (i-a[i]+n >= 0) pk[i-a[i]+n].push_back(i);
if (i+a[i]+n < 3*n) nk[i+a[i]+n].push_back(i);
}
for (int i = 0; i < 3*n; i++) reverse(nk[i].begin(), nk[i].end());
for (int j = 0; j < n; j++) if (a[j] <= n) {
int szpk = (int)pk[j-a[j]+n].size();
int sznk = (int)nk[j+a[j]+n].size();
if (szpk < sznk) {
vi &sm = pk[j-a[j]+n];
for (int i : sm) {
if (i == j) break;
int l = j-i;
int k = j+a[i];
int r = k-j;
if (k < 0 || k >= n) continue;
if (r == a[i] && l == a[k] && l != r) ans++;//, cout << i << " " << j << " " << k << endl;
}
}
else {
vi &sm = nk[j+a[j]+n];
for (int k : sm) {
if (k == j) break;
int r = k-j;
int i = j-a[k];
int l = j-i;
if (i < 0 || i >= n) continue;
if (r == a[i] && l == a[k] && l != r) ans++;//, cout << i << " " << j << " " << k << endl;
}
}
}
return ans;
}
std::vector<int> construct_range(int n, int k) {
if (n == 20) {
//vector<pair<int, vi>> dp(1);
//for (int i = 0; i < n; i++) {
// vector<pair<int, vi>> dp2;
// for (int h = 1; h < 10; h++) for (auto [_, a] : dp) {
// a.push_back(h);
// int cnt = i >= 3 ? count_triples(a) : 0;
// dp2.push_back({cnt, a});
// }
// sort(dp2.rbegin(), dp2.rend());
// while (dp2.size() > 10000) dp2.pop_back();
// swap(dp, dp2);
// cout << "Done: " << i << endl;
//}
//return dp[0].second;
return {5, 2, 3, 3, 1, 2, 1, 4, 3, 2, 7, 6, 5, 6, 3, 4, 1, 2, 1, 3};
}
vi ans = {1, 1, 1};
int mx = 0;
for (int t = 1; t*n < 6e5; t++) {
srand(42*t);
set<int> s;
while ((int)s.size()*(int)s.size() < 6*n) s.insert(((rand()%(int)(3/2.0*n)-n/4))/2*2);
vi pts(s.begin(), s.end()), a(n, 1e9);
int m = (int)pts.size();
for (int i = 0; i < m; i++) for (int j = i+1; j < m; j++) if ((pts[i]+pts[j])/2 >= 0 && (pts[i]+pts[j])/2 < n) a[(pts[i]+pts[j])/2] = min(a[(pts[i]+pts[j])/2], (abs(pts[i]-pts[j]))/2);
for (int i = 0; i < n; i++) if (a[i] == 1e9) a[i] = (rand()&1)+1;
int count = count_triples(a);
if (count > mx) mx = count, ans = a;
}
//cout << "Score: " << setprecision(2) << fixed << (mx/(float)k) << endl;
return ans;
}
