#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
vector<ll> h;
unordered_set<ll> ans;
ll mul = 1e6;
ll SQ = 0;
void comp(ll i, ll j, ll k)
{
if (i == j || i == k || j == k)
return;
vector<ll> v = {abs(i - j), abs(i - k), abs(j - k)}, v2 = {h[i], h[j], h[k]};
ll has = 0;
sort(all(v));
sort(all(v2));
if (v == v2)
{
vector<ll> ret = {i, j, k};
sort(all(ret));
if (ret[1] - ret[0] == ret[2] - ret[1] && h[ret[1]] == ret[2] - ret[0])
return;
has = ret[0] * mul * mul + ret[1] * mul + ret[2];
ans.insert(has);
}
}
long long count_triples(std::vector<int> H)
{
ans.clear();
h.resize(0);
SQ=0;
mul=1e6;
for (auto k : H)
h.pb(k);
ll i, j, k, a, b, a2, b2, c, c2;
auto calc = [&]()
{
b = a - h[a];
if (b >= 0)
comp(k, a, b);
b2 = a + h[a];
if (b2 < sz(h))
comp(k, a, b2);
c = k - h[a];
if (c >= 0)
comp(k, a, c);
c = k + h[a];
if (c < sz(h))
comp(k, a, c);
};
for (k = 0; k < sz(h); k++)
{
a = k - h[k];
if (a >= 0)
calc();
a2 = k + h[k];
if (a2 < sz(h))
{
a = a2;
calc();
}
}
ll ag = 0, tot, ca, act = 0;
vector<vector<ll>> ordR(sz(h) * 2), ordL(sz(h) * 2);
vector<ll> vis(sz(h) * 2, -1), R(sz(h)), L(sz(h));
for (i = 0; i < sz(h); i++)
{
ordR[i + h[i]].pb(i);
ordL[i - h[i] + sz(h)].pb(i);
R[i]=i+h[i];
L[i]=i-h[i]+sz(h);
}
for (i = 0; i < sz(h) * 2; i++)
{
act++;
for (auto &x : ordL[i])
vis[h[x]] = act;
for (auto &x : ordL[i])
{
if (sz(ordL[i]) >= sz(ordR[R[x]]))
{
for (auto &y : ordR[R[x]])
{
if (h[x] > h[y] && vis[h[x] - h[y]]==act)
ag++;
}
}
}
act++;
for (auto &x : ordR[i])
vis[h[x]] = act;
for (auto &x : ordR[i])
{
if (sz(ordR[i]) > sz(ordL[L[x]]))
{
for (auto &y : ordL[L[x]])
{
if (h[x] > h[y] && vis[h[x] - h[y]]==act)
ag++;
}
}
}
}
return ag + sz(ans);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
std::vector<int> construct_range(int M, int K) {
vector<int>ans2;
ll ma=0, ret;
for(ll mid=1; mid<M; mid++)
{
ll act, i, band=0;
act=mid;
vector<int>v(M);
for(i=0; i<M; i++)
{
if(act>0&&!band)
v[i]=act--;
else if(act<=mid&&band)
v[i]=act++;
else
{
if(!band)
{
v[i]=mid+1;
band=1;
act=1;
}
else
{
i--;
band=0;
act=mid;
}
}
}
ret=count_triples(v);
if(ret>ma)
{
ma=ret;
ans2=v;
}
}
return ans2;
}
