#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
random_device rnd;
mt19937 mt(rnd());
double mtd(){return (0.0+mt())/numeric_limits<unsigned int>::max();}
bool test = true;
long long count_triples(std::vector<int> H) {
int N = H.size();
long long answer = 0;
if(N <= 200000){
long long n1 = N,n2 = n1*n1;
unordered_set<long long> S;
for(int i=0; i<N; i++){
long long k = i-H.at(i);
if(k >= 0){
vector<long long> L = {i+H.at(k),i-H.at(k),k+H.at(k),k-H.at(k)};
sort(L.begin(),L.end());
L.erase(unique(L.begin(),L.end()),L.end());
for(auto l : L){
if(l < 0 || l >= N) continue;
if(l == i || l == k) continue;
int a = i,b = k,c = l;
if(a > b) swap(a,b);
if(b > c) swap(b,c);
if(a > b) swap(a,b);
int h1 = H.at(i),h2 = H.at(k),h3 = H.at(l);
if(max({h1,h2,h3}) == h2 && (b-a == h3 || c-b == h1)) continue;
if(S.count(a*n2+b*n1+c)) continue;
S.insert(a*n2+b*n1+c);
if(h1 > h2) swap(h1,h2);
if(h2 > h3) swap(h2,h3);
if(h1 > h2) swap(h1,h2);
answer += (h3 == c-a && ((h1 == b-a && h2 == c-b) || (h1 == c-b && h2 == b-a)));
}
}
k = i+H.at(i);
if(k < N){
vector<long long> L = {i+H.at(k),i-H.at(k),k+H.at(k),k-H.at(k)};
sort(L.begin(),L.end());
L.erase(unique(L.begin(),L.end()),L.end());
for(auto l : L){
if(l < 0 || l >= N) continue;
if(l == i || l == k) continue;
int a = i,b = k,c = l;
if(a > b) swap(a,b);
if(b > c) swap(b,c);
if(a > b) swap(a,b);
int h1 = H.at(i),h2 = H.at(k),h3 = H.at(l);
if(max({h1,h2,h3}) == h2 && (b-a == h3 || c-b == h1)) continue;
if(S.count(a*n2+b*n1+c)) continue;
S.insert(a*n2+b*n1+c);
if(h1 > h2) swap(h1,h2);
if(h2 > h3) swap(h2,h3);
if(h1 > h2) swap(h1,h2);
answer += (h3 == c-a && ((h1 == b-a && h2 == c-b) || (h1 == c-b && h2 == b-a)));
}
}
}
vector<pair<int,int>> G(N);
vector<int> L(N),R(N);
for(int i=0; i<N; i++) G.at(i) = {H.at(i)-i+N,H.at(i)-(N-1-i)+N};
int zero = 0;
for(int i=0; i<N; i++){
int h = H.at(i);
L.at(i) = h+zero;
zero--;
}
zero = 0;
for(int i=N; i--;){
int h = H.at(i);
R.at(i) = h+zero;
zero--;
}
vector<vector<int>> Cr(N+N),Cl(N+N);
for(int i=N-1; i>=0; i--){
int r = R.at(i)+N;
Cr.at(r).push_back(i);
}
for(int i=0; i<N; i++){
int l = L.at(i)+N,r = R.at(i)+N;
Cr.at(r).pop_back();
auto [nowl,nowr] = G.at(i);
if(Cl.at(nowl).size() <= Cr.at(nowr).size()){
for(auto posl : Cl.at(nowl)){
int posr = posl+H.at(i);
if(posr >= N) break;
if(posl < i && i < posr){
int h1 = H.at(posl),h2 = H.at(i),h3 = H.at(posr);
answer += (posr-i == h1 && i-posl == h3);
}
}
}
else{
for(auto posr : Cr.at(nowr)){
int posl = posr-H.at(i);
if(posl < 0) continue;
if(posl < i && i < posr){
int h1 = H.at(posl),h2 = H.at(i),h3 = H.at(posr);
answer += (posr-i == h1 && i-posl == h3);
}
}
}
Cl.at(l).push_back(i);
}
}
return answer;
}
double timelimit = 55*CLOCKS_PER_SEC;
std::vector<int> construct_range(int M, int K) {
double starttime = clock();
vector<int> ret;
while(ret.size() < M){
for(auto v : {1,2,1,4,3,2,3,1,1,2}) ret.push_back(v);
}
return ret;
auto bestret = ret;
long long now = count_triples(ret);
long long best = now;
double starttemp = 2,endtemp = 0.2;
while(now < K){
double time = clock()-starttime;
if(time > timelimit) break;
int kind = mt()%3;
if(kind == 0){
int pos = mt()%M,v = mt()%(M/2)+1;
int memo = ret.at(pos);
ret.at(pos) = v;
long long next = count_triples(ret);
double temp = starttemp+(endtemp-starttemp)/timelimit;
double prob = exp((next-now)/temp);
if(mtd() < prob){
now = next;
if(now > best) now = best,bestret = ret;
}
else ret.at(pos) = memo;
}
else if(kind == 1){
int pos = mt()%M,pos2 = pos;
while(pos == pos2) pos2 = mt()%M;
swap(ret.at(pos),ret.at(pos2));
long long next = count_triples(ret);
double temp = starttemp+(endtemp-starttemp)/timelimit;
double prob = exp((next-now)/temp);
if(mtd() < prob){
now = next;
if(now > best) now = best,bestret = ret;
}
else swap(ret.at(pos),ret.at(pos2));
}
else{
int pos = mt()%M,pos2 = pos,pos3 = pos;
while(pos == pos2) pos2 = mt()%M;
while(pos == pos3 || pos2 == pos3) pos3 = mt()%M;
swap(ret.at(pos),ret.at(pos2)),swap(ret.at(pos2),ret.at(pos3));
long long next = count_triples(ret);
double temp = starttemp+(endtemp-starttemp)/timelimit;
double prob = exp((next-now)/temp);
if(mtd() < prob){
now = next;
if(now > best) now = best,bestret = ret;
}
else swap(ret.at(pos2),ret.at(pos3)),swap(ret.at(pos),ret.at(pos2));
}
}
return bestret;
}
