#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));
}
}
std::vector<std::vector<int>> p(4 * 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)
s[i].insert(std::pair<int, int>(j, k));
}
p[3 * n + i - H[i]].push_back(i);
}
std::vector<std::vector<int>> p2(2 * n, std::vector<int>());
for (int j = n - 1; j > 0; j--)
{
p[3 * n + j - H[j]].pop_back();
if (p[3 * n + j - H[j]].size() < p2[j + H[j]].size())
{
for (int i : p[3 * n + j - H[j]])
{
int k = i + H[j];
if (k < n && k > j && H[k] + i == j && j + H[i] == k)
s[i].insert(std::pair<int, int>(j, k));
}
}
else
{
for (int k : p2[j + H[j]])
{
int i = k - H[j];
if (i >= 0 && i < j && H[k] + i == j && j + H[i] == k)
s[i].insert(std::pair<int, int>(j, k));
}
}
p2[j + H[j]].push_back(j);
}
long long ans = 0;
for (int i = 0; i < s.size(); i++)
{
ans += s[i].size();
}
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;
}
