#include "triples.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
typedef long long int lld;
int h[1000000];
int n;
vector<int> Pts[1000000];
set<int> S[1000000];
bool test(int a, int b, int c){
if(0<=a && a<b && b<c && c<n){
vector<int> X={b-a,c-a,c-b};
sort(X.begin(),X.end());
vector<int> Y={h[a],h[b],h[c]};
sort(Y.begin(),Y.end());
rep(i,0,3){
if(X[i]!=Y[i])return false;
}
// cout<<a<<" "<<b<<" "<<c<<endl;
return true;
}return false;
}
long long count_triples(std::vector<int> H) {
lld ans=0;
n=H.size();
rep(i,0,n)h[i]=H[i];
rep(i,0,3*n)S[i].clear(),Pts[i].clear();
// lld ans2=0;
// rep(a,0,n){
// rep(b,a+1,n){
// rep(c,b+1,n){
// int res=test(a,b,c);
// ans2+=res;
// }
// }
// }
rep(i,0,n){
int Nx=i+H[i];
if(Nx<n){
ans+=test(i,i+H[Nx],Nx);
if(i+H[Nx]!=Nx-H[Nx]){
ans+=test(i,Nx-H[Nx],Nx);
}
}
}
rep(i,0,n){
int Pr=i-H[i];
if(Pr>=0){
ans+=test(Pr,Pr+H[Pr],i);
if(Pr+H[Pr]!=i-H[Pr]){
ans+=test(Pr,i-H[Pr],i);
}
}
}
rep(i,0,n){
int Nx=i+H[i];
if(H[Nx]!=2*H[i]){
ans+=test(i,Nx,i+H[Nx]);
}
}
// vector<pair<int,int> >P;
rep(i,0,n){
int X=i-H[i]+n;
int Y=i+H[i]+n;
if(0<=X && X<3*n && 0<=Y && Y<3*n)Pts[X].push_back(Y);
}
// int A=0;
// trav(a,P){
// trav(b,P){
// trav(c,P){
// if(a!=b && b!=c && a!=c){
// if(b.first==a.first && b.second==c.second && a.second==c.first){
// A++;
// cout<<"2 "<<(a.first+a.second)/2<<" "<<(b.first+b.second)/2<<" "<<(c.first+c.second)/2<<endl;
// }
// }
// }
// }
// }
// cout<<A<<endl;
rep(i,0,3*n){
trav(a,Pts[i]){
if(S[i].size()<S[a].size()){
trav(b,S[i]){
ans+=(S[a].find(b)!=S[a].end());
}
}else{
trav(b,S[a]){
ans+=(S[i].find(b)!=S[i].end());
}
}
}
trav(a,Pts[i]){
S[a].insert(i);
}
}
// cout<<ans<<" "<<ans2<<endl;
return ans;
}
bool isprime(int x){
for(int i=2;i*i<=x;i++){
if(x%i==0)return false;
}
return true;
}
std::vector<int> construct_range(int M, int K) {
lld sq=1;
while(true){
if(4*(sq+1)*(sq+1)>M)break;
sq++;
}
while(!isprime(sq)){
sq--;
}
vector<int> V;
for(lld i=0;i<sq;i++){
int u=(i*i)%sq;
u=sq-u;
u%=sq;
V.push_back(i+2*sq*u);
}
sort(V.begin(),V.end());
vector<int> V2;
vector<int> sol(M,1);
rep(i,0,M){
if(i%2==0)sol[i]=1;
else sol[i]=2;
}
// cerr<<V.size()<<endl;
rep(i,0,V.size()){
rep(j,i+1,V.size()){
V2.push_back(V[i]+V[j]);
sol[V[i]+V[j]]=(V[j]-V[i]);
}
}
sort(V2.begin(),V2.end());
rep(i,1,V2.size()){
assert(V2[i]!=V2[i-1]);
// assert(V2[i]!=V2[i-1]+1);
}
// cout<<1<<endl;
return sol;
}
