//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"
bool same(int a1, int a2, int a3, int b1, int b2, int b3){
vi a(3);
vi b(3);
a[0] = a1, a[1] = a2, a[2] = a3, b[0] = b1, b[1] = b2, b[2] = b3;
sort(a.begin(), a.end()), sort(b.begin(),b.end());
for (int i = 0; i < 3; i++) if (a[i] != b[i]) return 0;
return 1;
}
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]];
//int o1 = res;
if (c < h[i]){
if (h[i-h[i]+c] == h[i] - c) res++;
if (c+c != h[i] && h[i-c] == h[i] - c) res++;
}
//if (res > o1) cout << i << " 1 " << h[i] << ' ' << c << ' ' << i-h[i] << '\n';
//o1 = res;
//largest center, right is right
c = h[i-h[i]];
if (c > h[i] && c <= i && h[i-c] == c - h[i]) res++;
//if (res > o1) cout << i << " 2 " << h[i] << ' ' << c << ' ' << i-h[i] << '\n';
}
//cout << res << '\n';
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 (c+c != h[i] && h[i+c] == h[i]-c) res++;
}
}
//cout << res << '\n';
//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] && h[j] * 2 != h[i]) 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] && h[j] * 2 != h[i]) res++;
}
lef[i1].insert(i);
}
/*ll c1 = 0;
for (int i = 0; i < n; i++) for (int j = i+1; j < n; j++){
int v1 = h[i];
int v2 = h[j];
if (v1 > v2) swap(v1,v2);
//missing longest
int c2 = c1;
if (i + v1 + v2 < n) c1 += same(v1,v2,h[i+v1+v2],j-i,i+v1+v2-j,v1+v2);
//v2 is longest
if (i+v2 < n) c1 += same(v1,v2,h[i+v2],j-i,i+v2-j,v2);
if (c1> c2) cout << i << " " << j << " " << v1 << " " << v2 << "\n";
}
cout << c1 << '\n';*/
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;
}
*/
