#include "triples.h"
#include <set>
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++;
}
}
}
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++;
}
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++;
}
}
}
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)
{
std::vector<int> ans(M, 1);
for (int i = 0; i < M; i++)
{
ans[i] = array[i % 14];
}
return ans;
}
