//IOI 2025 Day 1 Problem B
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define sz(x) (int) (x).size()
#define vi vector<int>
#define f first
#define s second
#include "triples.h"
long long count_triples(vi h){
int n = sz(h);
ll res = 0;
for (int i = 0; i < n; i++){
//largest right
if (h[i] > i) continue;
int c = h[i-h[i]];
if (c < h[i]){
if (h[i-h[i]+c] == h[i] - c) res++;
if (h[i-c] == h[i] - c) res++;
}
//largest center, right is right
c = h[i-h[i]];
if (c > h[i] && h[i-c] == c - h[i]) res++;
}
for (int i = 0; i < n; i++){
//largest left
if (h[i]+i >= n) continue;
int c = h[i+h[i]];
if (c < h[i]){
if (h[i+h[i]-c] == h[i]-c) res++;
if (h[i+c] == h[i]-c) res++;
}
}
//cout << res << '\n';
//largest center, left is right and right is left
//i-h[i], i+h[i]
set<int> lef[2*n];
set<int> rig[2*n];
for (int i = 0; i < n; i++) rig[h[i]+i].insert(i);
for (int i = 0; i < n; i++){
rig[h[i]+i].erase(i);
int i1 = i-h[i]+n;
int i2 = h[i]+i;
// cout << i << " " << i1 << " " << i2 << '\n';
if (sz(lef[i1]) < sz(rig[i2])){
//cout << "Checkign left\n";
for (int j : lef[i1]) if (i+h[j] < n && h[i+h[j]] == h[i] - h[j]) res++;
} else {
//cout << "Checking right " << *rig[i2].begin() << '\n';
for (int j : rig[i2]) if (i-h[j] >= 0 && h[i-h[j]] == h[i] - h[j]) res++;
}
lef[i1].insert(i);
}
return res;
}
vi construct_range(int m, int k){
return {};
}
/*
namespace {
void run_part1() {
int N;
assert(1 == scanf("%d", &N));
std::vector<int> H(N);
for (int i = 0; i < N; i++)
assert(1 == scanf("%d", &H[i]));
fclose(stdin);
long long T = count_triples(H);
printf("%lld\n", T);
fclose(stdout);
}
void run_part2() {
int M, K;
assert(2 == scanf("%d %d", &M, &K));
fclose(stdin);
std::vector<int> H = construct_range(M, K);
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() {
int part;
assert(1 == scanf("%d", &part));
if (part == 1)
run_part1();
else if (part == 2)
run_part2();
return 0;
}
*/
