#include "triples.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 rngl(chrono::steady_clock::now().time_since_epoch().count());
// #define int long long
// #define int unsigned long long
// #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
// #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>
// const ll mod = 1e9 + 7;
// const ll mod = 998244353;
const ll inf = 1e9;
const ll biginf = 1e18;
const int maxN = 2 * 1e5 + 15;
const int sq = 450;
vector<int> v[2 * maxN];
ll count_triples(vector<int> h) {
ll ans = 0;
int n = h.size();
for (int i = 0; i < n; i++) {
int k = i + h[i];
if (k < 0 || k >= n) continue;
int j = h[k] + i;
if (j < 0 || j >= n) continue;
ans += (h[i] == h[j] + h[k]);
}
for (int i = 0; i < n; i++) {
int k = i + h[i];
if (k < 0 || k >= n) continue;
int j = k - h[k];
if (j < 0 || j >= n) continue;
ans += (h[i] == h[j] + h[k] && h[j] != h[k]);
}
for (int k = 0; k < n; k++) {
int i = k - h[k];
if (i < 0 || i >= n) continue;
int j = h[i] + i;
if (j < 0 || j >= n) continue;
ans += (h[k] == h[i] + h[j]);
}
for (int k = 0; k < n; k++) {
int i = k - h[k];
if (i < 0 || i >= n) continue;
int j = k - h[i];
if (j < 0 || j >= n) continue;
ans += (h[k] == h[i] + h[j] && h[i] != h[j]);
}
for (int i = 0; i < n; i++) {
int j = i + h[i];
if (j < 0 || j >= n) continue;
int k = h[j] + i;
if (k < 0 || k >= n) continue;
ans += (h[j] == h[i] + h[k] && h[i] != h[k]);
}
// return ans;
for (int i = 0; i < n; i++)
v[h[i] - i + n].pb(i);
for (int t = 0; t <= 2 * n; t++) {
if (v[t].size() <= sq) {
for (int i = 0; i < v[t].size(); i++) {
for (int j = i + 1; j < v[t].size(); j++) {
int k = h[v[t][i]] + v[t][j];
if (k < 0 || k >= n) continue;
ans += (h[v[t][i]] == k - v[t][j] && h[v[t][j]] == k - v[t][i] && h[k] == v[t][j] - v[t][i]);
}
}
} else {
for (int k = 0; k < n; k++) {
int x = t - n, y = k - x;
if (h[k] % 2 == y % 2) {
int i = (y - h[k]) / 2;
int j = (y + h[k]) / 2;
ans += (0 <= i && i < n && 0 <= j && j < n && h[i] - i == x && h[j] - j == x);
}
}
}
}
return ans;
}
vector<int> construct_range(int m, int k) {
vector<int> ans(m);
for (int i = 0; i < m; i++)
ans[i] = (i % 3 ? 1 : 2);
return ans;
}
// namespace {
// // BEGIN SECRET
// const std::string input_secret = "jB7KRtelfNrzhva6IhSoGAcDptqeBHJr";
// const std::string output_secret = "qOpG8GoYprN2GHwBEAOkfIfpiiFWanMx";
// const std::string extra_secret = "nxz3K1mLpvlEac8SbN9hu4cFQ2jnBxG9";
// // END SECRET
// void run_part1() {
// int N;
// assert(1 == scanf("%d", &N));
// std::vector<int> H(N);
// for (int i = 0; i < N; i++)
// scanf("%d", &H[i]);
// fclose(stdin);
// long long T = count_triples(H);
// // BEGIN SECRET
// printf("%s\n", output_secret.c_str());
// printf("OK\n");
// // END SECRET
// printf("%lld\n", T);
// fclose(stdout);
// }
// void run_part2() {
// int M, K;
// assert(2 == scanf("%d %d", &M, &K));
// fclose(stdin);
// // BEGIN SECRET
// printf("%s\n", output_secret.c_str());
// // END SECRET
// std::vector<int> H = construct_range(M, K);
// // BEGIN SECRET
// printf("%s\n", extra_secret.c_str());
// // END SECRET
// int N = H.size();
// printf("%d\n", N);
// for (int i = 0; i < N; i++)
// printf("%d%c", H[i], " \n"[i + 1 == N]);
// fclose(stdout);
// }
// } // namespace
// int main() {
// // BEGIN SECRET
// char secret[1000];
// assert(1 == scanf("%999s", secret));
// if (std::string(secret) != input_secret) {
// printf("%s\n", output_secret.c_str());
// printf("PV\n");
// printf("Possible tampering with the input\n");
// fclose(stdout);
// return 0;
// }
// // END SECRET
// int part;
// assert(1 == scanf("%d", &part));
// if (part == 1)
// run_part1();
// else if (part == 2)
// run_part2();
// // BEGIN SECRET
// else {
// printf("%s\n", output_secret.c_str());
// printf("PV\n");
// printf("Possible tampering with the input\n");
// fclose(stdout);
// return 0;
// }
// // END SECRET
// return 0;
// }
