#include "triples.h"
#include <set>
#include <cstdio>
long long count_triples(std::vector<int> H)
{
int n = H.size();
// if (n < 1000000)
// return 0;
std::vector<std::set<std::pair<int, int>>> s(n, std::set<std::pair<int, int>>());
for (int j = 1; j < n - 1; j++)
{
int i, k;
i = j - H[j];
if (i >= 0)
{
k = j + H[i];
if (k < n && k - i == H[k])
s[i].insert(std::pair<int, int>(j, k));
k = i + H[i];
if (k < n && k > j && H[k] == k - j)
s[i].insert(std::pair<int, int>(j, k));
}
k = j + H[j];
if (k < n)
{
i = j - H[k];
if (i >= 0 && k - i == H[i])
s[i].insert(std::pair<int, int>(j, k));
i = k - H[k];
if (i >= 0 && i < j && j - i == H[i])
s[i].insert(std::pair<int, int>(j, k));
}
}
long long ans = 0;
for (int i = 0; i < s.size(); i++)
{
ans += s[i].size();
}
std::vector<std::vector<int>> l(n, std::vector<int>());
std::vector<std::vector<int>> r(n, std::vector<int>());
for (int i = 0; i < n; i++)
{
int j = i + H[i];
if (j < n)
{
int k = i + H[j];
if (k < n && k > j && k - H[k] == j)
ans++;
l[j].push_back(i);
}
{
int k = i - H[i];
if (k >= 0)
r[k].push_back(i);
}
}
for (int jj = 0; jj < n; jj++)
{
if (l[jj].size() == 0 || r[jj].size() == 0)
continue;
if (1LL * l[jj].size() * r[jj].size() <= n)
{
for (const int &i : l[jj])
{
for (const int &k : r[jj])
{
if (H[i] == H[k])
continue;
int j = i + H[k];
if (H[j] == k - i)
{
ans++;
// printf("%d %d\n", j, i + H[i]);
}
}
}
}
else
{
for (int j = jj - 1; j >= 0; j--)
{
int d = jj - j;
if (d < H[j])
continue;
d += H[j];
if ((d & 1) == 1)
continue;
d >>= 1;
int x = H[j] - d;
if (x == d)
continue;
int i = jj - d;
int k = jj + x;
if (k - H[k] == jj && i + H[i] == jj)
{
ans++;
// printf("%d %d\n", j, i + H[i]);
}
}
for (int j = jj + 1; j < n; j++)
{
int d = j - jj;
if (d < H[j])
continue;
d += H[j];
if ((d & 1) == 1)
continue;
d >>= 1;
int x = H[j] - d;
if (x == d)
continue;
int i = jj - x;
int k = jj + d;
if (k - H[k] == jj && i + H[i] == jj)
{
ans++;
// printf("%d %d\n", j, i + H[i]);
}
}
}
}
return ans;
}
int array[] = {3, 1, 2, 1, 4, 3, 2, 7, 6, 5, 6, 3, 4, 5};
std::vector<int> construct_range(int M, int K)
{
if (M < 30)
{
std::vector<int> ans(M, 1);
for (int i = 0; i < M; i++)
{
ans[i] = array[i % 14];
}
return ans;
}
else
{
std::vector<int> ans(M, 0);
std::vector<int> s(2 * M, 2);
std::vector<int> z(0);
std::vector<bool> f(2 * M, false);
f[0] = true;
s[1] = -1000000;
z.push_back(-1);
z.push_back(1);
ans[0] = 1;
int count = 1;
while (count < M)
{
int y = 1;
for (int i = 3; i < s.size(); i += 2)
{
if (s[y] < s[i])
y = i;
}
for (int &x : z)
{
if (x < y && y + x < 2 * M && !f[y + x])
{
ans[(y + x) / 2] = (y - x) / 2;
count++;
f[y + x] = true;
for (int &q : z)
{
int w = y + x - q;
if (w >= q && w < 2 * M)
{
s[w]--;
}
}
}
}
z.push_back(y);
for (int i = y + 2; i + y < s.size(); i += 2)
if (!f[i + y] && i + y < 2 * M)
s[i]++;
s[y] = -1000000;
// print(ans, s, 1);
}
return ans;
}
}
void print(std::vector<int> H, std::vector<int> s, int mod)
{
int N = H.size();
std::vector<int> X(N), Y(N);
int maxx = 0, minx = N, maxy = 0, miny = N;
printf("%d\n", N);
for (int i = 0; i < N; i++)
{
X[i] = i - H[i];
Y[i] = i + H[i];
if (H[i] == 0)
{
Y[i] = 1;
X[i] = -1;
}
maxx = std::max(maxx, X[i]);
minx = std::min(minx, X[i]);
maxy = std::max(maxy, Y[i]);
miny = std::min(miny, Y[i]);
printf("%d%c", H[i], " \n"[i + 1 == N]);
}
int sizex = maxx - minx + 1;
int sizey = maxy - miny + 1;
std::vector<std::vector<char>> map(sizey, std::vector<char>(sizex, ' '));
std::vector<int> F(sizey);
for (int i = 0; i < N; i++)
{
F[maxy - Y[i]] = Y[i];
map[maxy - Y[i]][X[i] - minx] = '*';
int x = X[i] - minx - 1;
int y = maxy - Y[i] - 1;
while (y >= 0 && x >= 0)
{
map[y][x] = '.';
y--;
x--;
}
}
for (int i = 0; i < sizey; i++)
{
if (F[i] != 0)
{
printf("%4d", F[i]);
}
else
{
printf(" ");
}
for (int j = 0; j < sizex; j++)
{
printf("%c", map[i][j]);
}
int y = maxy - i;
if (!s.empty() && y % 2 == mod)
{
printf("%d", s[y]);
}
printf("\n");
}
printf("%d\n", minx);
}
