#include<bits/stdc++.h>
#include "triples.h"
#define TIME (1.0* clock()/CLOCKS_PER_SEC)
#define pb push_back
#define eb emplace_back
#define id1 (id<<1)
#define id2 (id<<1)|1
#define ll long long
//#define ii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<long long>
#define vll vector <pair<ll,ll>>
#define li pair<long long,int>
#define vil vector <pair<int,ll>>
#define db double
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for (int i = (a); i <=(b); i++)
#define F0R(i, a) FOR(i, 0, a-1)
#define ROF(i, a, b) for (int i = (b); i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a-1)
#define rep(a) F0R(_, a)
#define each(a, x) for (auto &a : x)
#define ALL(x) (x).begin(),(x).end()
#define pq priority_queue <li, vector <li>, greater <li>>
using namespace std;
const int maxn=1e6;
//const int MOD=1e9+7;
//const int MOD=998244353;
//const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
long long count_triples(std::vector<int> H){
int N = (int)H.size();
if(N < 3) return 0;
// plus[p] = indices i with i + H[i] == p
// minus[p] = indices i with i - H[i] == p
vector<vector<int>> plus(N), minus(N);
for(int i = 0; i < N; ++i){
int p = i + H[i];
if(p >= 0 && p < N) plus[p].push_back(i);
int q = i - H[i];
if(q >= 0 && q < N) minus[q].push_back(i);
}
vector<int> cnt(N+1, 0);
vector<int> touched;
ll ans = 0;
for(int j = 0; j < N; ++j){
// case 1: i = j - H[j], k in minus[j], check H[i] == H[j] + H[k]
int i = j - H[j];
if(i >= 0){
for(int k : minus[j]){
if(H[i] == H[j] + H[k]) ans++;
}
}
// case 3: k = j + H[j], i in plus[j], check H[k] == H[i] + H[j]
int k = j + H[j];
if(k < N){
for(int ii : plus[j]){
if(H[k] == H[ii] + H[j]) ans++;
}
}
// case 2: j is the largest (a+b). need pairs (i in plus[j], k in minus[j]) with H[i] + H[k] == H[j]
auto &L = plus[j];
auto &R = minus[j];
if(!L.empty() && !R.empty()){
if(L.size() <= R.size()){
for(int ii : L){
int v = H[ii];
if(v >= 0 && v <= N) {
if(cnt[v] == 0) touched.push_back(v);
cnt[v]++;
}
}
for(int kk : R){
int need = H[j] - H[kk];
if(need >= 0 && need <= N) ans += cnt[need];
}
} else {
for(int kk : R){
int v = H[kk];
if(v >= 0 && v <= N) {
if(cnt[v] == 0) touched.push_back(v);
cnt[v]++;
}
}
for(int ii : L){
int need = H[j] - H[ii];
if(need >= 0 && need <= N) ans += cnt[need];
}
}
for(int v : touched) cnt[v] = 0;
touched.clear();
}
}
return ans;
}
vector<int> construct_range(int M, int K){
if(M < 3) {
return vector<int>(3,1);
}
int s_size = max(2, (int)(sqrt((double)M) * 2.0));
s_size = min(s_size, M);
vector<int> Hmap(M, -1);
vector<char> used(M, 0);
int filled = 0;
int maxUsedIdx = -1;
for(int a = 0; a < s_size && filled < M; ++a){
for(int b = a+1; b < s_size && filled < M; ++b){
int i = a + b;
if(i >= M) continue;
if(used[i]) continue;
int h = b - a;
if(h <= 0) continue;
Hmap[i] = h;
used[i] = 1;
++filled;
if(i > maxUsedIdx) maxUsedIdx = i;
}
}
int a_start = s_size;
int s_limit = min(M, (int)max( (double)s_size*4.0, (double)s_size+500.0 ));
for(int a = a_start; a < s_limit && filled < M; ++a){
for(int b = 0; b < a && filled < M; ++b){
int i = a + b;
if(i >= M) continue;
if(used[i]) continue;
int h = a - b;
if(h <= 0) continue;
Hmap[i] = h;
used[i] = 1;
++filled;
if(i > maxUsedIdx) maxUsedIdx = i;
}
}
if(filled < M){
int extra_limit = min(M, 2000);
for(int a = 0; a < extra_limit && filled < M; ++a){
for(int b = a+1; b < extra_limit && filled < M; ++b){
int i = a + b + 1;
if(i >= M) continue;
if(used[i]) continue;
int h = b - a;
if(h <= 0) continue;
Hmap[i] = h;
used[i] = 1;
++filled;
if(i > maxUsedIdx) maxUsedIdx = i;
}
}
}
int N;
if(maxUsedIdx == -1){
N = min(3, M);
return vector<int>(N, 1);
} else {
N = max(3, maxUsedIdx + 1);
if(N > M) N = M;
}
vector<int> H(N, 1);
for(int i = 0; i < N; ++i){
if(used[i]){
int hv = Hmap[i];
if(hv <= 0) hv = 1;
if(hv >= N) hv = N-1;
H[i] = hv;
} else {
H[i] = 1;
}
}
for(int i = 0; i < N; ++i){
if(H[i] < 1) H[i] = 1;
if(H[i] > N-1) H[i] = N-1;
}
return H;
}
