#include "triples.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool maximize(T& a, T b){
if(a < b){
a = b;
return true;
}
return false;
}
const int lim = 2e5 + 5;
namespace sub123456{
vector<int>h;
int n;
bool check(int i, int j, int k){
if(i >= j || j >= k || i < 0 || k >= n){
return false;
}
vector<int>D = {j - i, k - j, k - i}, H = {h[i], h[j], h[k]};
if(D[0] > D[1]){
swap(D[0], D[1]);
}
if(H[0] > H[1]){
swap(H[0], H[1]);
}
if(H[1] > H[2]){
swap(H[1], H[2]);
}
if(H[0] > H[1]){
swap(H[0], H[1]);
}
return D == H;
}
namespace sub1{
ll solve(){
int ans = 0;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
for(int k = j + 1; k < n; k++){
ans += check(i, j, k);
}
}
}
return ans;
}
}
namespace sub2{
ll solve(){
int ans = 0;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < min(i + 11, n); j++){
for(int k = j + 1; k < min(i + 11, n); k++){
ans += check(i, j, k);
}
}
}
return ans;
}
}
namespace sub3{
ll solve(){
int ans = 0;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(check(i, j, i + h[i])){
ans++;
}
if(check(i, j, j + h[i])){
ans++;
}
if(h[i] != h[j]){
if(i + h[j] != j + h[i] && check(i, j, i + h[j])){
ans++;
}
if(j + h[j] != i + h[i] && check(i, j, j + h[j])){
ans++;
}
}
}
}
return ans;
}
}
namespace sub4{
bool check_subtask(){
for(int i = 1; i < n; i++){
if(h[i] < h[i - 1]){
return false;
}
}
return true;
}
ll solve(){
int ans = 0;
for(int k = 2; k < n; k++){
if(k >= h[k]){
int i = k - h[k];
if(check(i, i + h[i], k)){
ans++;
}
if(i + h[i] != k - h[i] && check(i, k - h[i], k)){
ans++;
}
}
}
return ans;
}
}
namespace sub56{
const int SIZE = 500;
vector<array<int, 3>>trivial;
void work(int i, int j, int k){
if(check(i, j, k) && (h[j] != k - i || h[i] != k - j || h[k] != j - i)){
trivial.push_back({i, j, k});
}
}
vector<int>minus_i[lim << 1], plus_k[lim << 1];
bitset<lim>bi[lim / SIZE + 5], bk[lim / SIZE + 5];
ll solve(){
for(int i = 0; i < n; i++){
if(i + h[i] < n){
int j = i + h[i], k = i + h[i];
work(i, j, i + h[j]);
work(i, j, j + h[j]);
work(i, i + h[k], k);
work(i, k - h[k], k);
}
}
for(int j = 0; j < n; j++){
if(j >= h[j]){
int i = j - h[j];
work(i, j, i + h[i]);
work(i, j, j + h[i]);
}
if(j + h[j] < n){
int k = j + h[j];
work(j - h[k], j, k);
work(k - h[k], j, k);
}
}
for(int k = 0; k < n; k++){
if(k >= h[k]){
int j = k - h[k], i = k - h[k];
work(j - h[j], j, k);
work(k - h[j], j, k);
work(i, i + h[i], k);
work(i, k - h[i], k);
}
}
ll ans = 0;
if(!trivial.empty()){
sort(trivial.begin(), trivial.end());
for(int i = ans = 1; i < trivial.size(); i++){
if(trivial[i] != trivial[i - 1]){
ans++;
}
}
}
for(int i = 0; i < n; i++){
minus_i[h[i] - i + lim].push_back(i);
plus_k[h[i] + i].push_back(i);
}
vector<int>heavy_i, heavy_k;
for(int i = 0; i < (lim << 1); i++){
if(minus_i[i].size() > SIZE){
heavy_i.push_back(i);
}
if(plus_k[i].size() > SIZE){
heavy_k.push_back(i);
}
}
for(int i = 0; i < heavy_i.size(); i++){
bi[i].reset();
}
for(int i = 0; i < heavy_k.size(); i++){
bk[i].reset();
for(int& j : plus_k[heavy_k[i]]){
bk[i][j] = true;
}
}
for(int j = 0; j < n; j++){
int vi = h[j] - j + lim, vk = h[j] + j;
if(minus_i[vi].size() > SIZE && plus_k[vk].size() > SIZE){
int pi = lower_bound(heavy_i.begin(), heavy_i.end(), vi) - heavy_i.begin(), pk = lower_bound(heavy_k.begin(), heavy_k.end(), vk) - heavy_k.begin();
bk[pk][j] = false;
ans += ((bi[pi] << h[j]) & bk[pk]).count();
bi[pi][j] = true;
}
else if(minus_i[vi].size() > SIZE){
int pi = lower_bound(heavy_i.begin(), heavy_i.end(), vi) - heavy_i.begin();
for(int& k : plus_k[vk]){
if(k >= max(j + 1, h[j])){
int i = k - h[j];
if(i < j && bi[pi][i]){
ans++;
}
}
}
bi[pi][j] = true;
}
else if(plus_k[vk].size() > SIZE){
int pk = lower_bound(heavy_k.begin(), heavy_k.end(), vk) - heavy_k.begin();
bk[pk][j] = false;
for(int& i : minus_i[vi]){
if(i == j){
break;
}
int k = i + h[j];
if(k > j && k < lim && bk[pk][k]){
ans++;
}
}
}
else{
for(int i = 0, k = 0; i < minus_i[vi].size() && minus_i[vi][i] < j; i++){
int si = minus_i[vi][i] + h[j];
if(si >= lim){
break;
}
if(si > j){
while(k < plus_k[vk].size() && plus_k[vk][k] < si){
k++;
}
if(k == plus_k[vk].size()){
break;
}
if(plus_k[vk][k] == si){
ans++;
}
}
}
}
}
return ans;
}
}
ll solve(vector<int>& _h){
swap(h, _h);
if((n = h.size()) <= 100){
return sub1::solve();
}
if(*max_element(h.begin(), h.end()) <= 10){
return sub2::solve();
}
if(n <= 2000){
return sub3::solve();
}
if(sub4::check_subtask()){
return sub4::solve();
}
return sub56::solve();
}
}
ll count_triples(vector<int>h){
return sub123456::solve(h);
}
namespace sub789101112{
int m;
vector<int>h;
bool check(int i, int j, int k){
if(i >= j || j >= k || i < 0 || k >= h.size()){
return false;
}
vector<int>D = {j - i, k - j, k - i}, H = {h[i], h[j], h[k]};
if(D[0] > D[1]){
swap(D[0], D[1]);
}
if(H[0] > H[1]){
swap(H[0], H[1]);
}
if(H[1] > H[2]){
swap(H[1], H[2]);
}
if(H[0] > H[1]){
swap(H[0], H[1]);
}
return D == H;
}
namespace sub7{
vector<int>solve(){
vector<int>ans;
int triple = -1;
for(int x = 1; x < 10; x++){
for(int y = 1; y < 10; y++){
for(int z = 1; z < 10; z++){
int sum = 0;
h = {x, y, z};
if(check(0, 1, 2)){
sum++;
}
for(int k = 3; k < m; k++){
h.push_back(-1);
int place, best = -1;
for(int v = 1; v <= k; v++){
h[k] = v;
int cnt = 0;
for(int i = 0; i < k; i++){
for(int j = i + 1; j < k; j++){
if(check(i, j, k)){
cnt++;
}
}
}
if(maximize(best, cnt)){
place = v;
}
}
h[k] = place;
sum += best;
}
if(maximize(triple, sum)){
swap(ans, h);
}
}
}
}
return ans;
}
}
namespace sub89{
bitset<lim>cur, in_s;
vector<int>solve(){
cur.reset();
in_s.reset();
vector<int>s = {0};
in_s[0] = true;
vector<pair<int, int>>xy;
while(xy.size() < m - 1){
int ci;
for(int i = 1, best = -1; i <= m; i++){
if(!in_s[i]){
int cnt = 0;
for(int& j : s){
if(i + j < m && !cur[i + j]){
cnt++;
}
}
if(maximize(best, cnt)){
ci = i;
}
}
}
in_s[ci] = true;
for(int& j : s){
if(ci + j < m && !cur[ci + j]){
xy.push_back(make_pair(min(ci, j), max(ci, j)));
cur[ci + j] = true;
}
}
s.push_back(ci);
}
vector<int>ans(m, 1);
for(auto& [x, y] : xy){
ans[x + y] = y - x;
}
return ans;
}
}
vector<int>M30000 = {0, 1, 2, 4, 7, 12, 20, 29, 38, 52, 73, 94, 127, 151, 181, 211, 257, 315, 373, 412, 475, 530, 545, 607, 716, 797, 861, 964, 1059, 1160, 1306, 1385, 1434, 1555, 1721, 1833, 1933, 2057, 2260, 2496, 2698, 2873, 3060, 3196, 3331, 3628, 3711, 3867, 4139, 4446, 4639, 5021, 5064, 5322, 5613, 6003, 6273, 6493, 6641, 6979, 7275, 7587, 8017, 8373, 9071, 9167, 9760, 10105, 10489, 11109, 11374, 11516, 12101, 12330, 12867, 13426, 13923, 14535, 14911, 13346, 14147, 15039, 13837, 9352, 10245, 11868, 13192, 14918, 12547, 8268, 8865, 11636, 14037, 11817, 14607, 14842, 6855, 11322, 6871, 10040, 12684, 7742, 14218, 11591, 13867, 14445, 14778, 4509, 9484, 14935, 10682, 13265, 11185, 14751, 4187, 12772, 4985, 5344, 14750, 9650, 14151, 11225, 15005, 14404, 11880, 3902, 13884, 4298, 6534, 8502, 13636, 7476, 14277, 12363, 14569, 7174, 12301, 14292, 7274, 14927, 2080, 3066, 10917, 11761, 2359, 14893, 5405, 5553, 13101, 13214, 3602, 12179, 6941, 9932, 14881, 12297, 310, 486, 13954, 14631, 473, 6196, 143, 13549, 2475, 14950, 11734, 2992, 6014, 14644, 2550, 15007, 10838, 9372, 1224, 7148, 14899, 831, 13004, 3757, 5775, 14882, 5346, 218, 8289, 14393, 3898, 2069, 14467, 6922, 14657, 9814, 1194, 8945, 14944, 14930, 1441, 3285, 10224, 13124, 1074, 13702, 176, 1710, 2615, 13919, 13473, 7149, 5175, 12185, 14992, 11145, 104, 144, 1218, 8418, 14660, 3509, 14707, 829, 7888, 14023, 14733, 4634, 179, 8441, 14902, 2826, 169, 227, 6603, 15040, 10749, 14872, 2490, 12796, 10014, 14378, 878, 1468, 9716, 13585, 14967, 769, 8113, 490, 8909, 13857, 11, 76, 14949, 12680, 8795, 105, 2432, 14957, 2363, 54, 7142, 10084, 4388, 13723, 14210, 5639, 14913, 1626, 3829, 5767, 7701, 198, 2012, 14922, 4771, 10505, 14406, 15, 713, 14833, 15016, 626, 3573, 4092, 14737, 5563, 281, 9398, 13158, 14474, 14932, 574, 3059, 1688, 8754, 14077, 13532, 7685, 158, 1150, 896, 3144, 10485, 12485, 13507, 14809, 194, 11277, 12035, 670, 2398, 9782, 728, 231, 5493, 7805, 1871, 10352, 15285, 12159, 1086, 13716, 14663, 273, 2940, 4066, 554, 9060, 13227, 1553, 11355, 14108, 14786, 12199, 1119, 4674, 14920, 51, 1525, 6497, 9646, 836, 12862, 14015, 699, 750, 6259, 14145, 13526, 2745, 11222, 68, 11227, 11624, 1965, 14784, 13184, 15017, 212, 14313, 14909, 1262, 4848, 484, 8607, 1498, 14096, 14678, 13186, 330, 2645, 153, 7043, 4506, 5862, 11483, 14477, 8716, 12489, 14868, 109, 1040, 599, 1776, 2123, 9172, 12133, 12681, 14986, 145, 14572, 4260, 8176, 14363, 24900, 395, 7183, 3054, 2286, 3498, 4973, 13661, 13813, 15352, 19631, 1370, 5025, 22780, 19955, 13, 3652, 33, 4510, 4905, 15049, 436, 14720, 18270, 12472, 14910, 362, 650, 2186, 7405, 21791, 2473, 10903, 20876, 1720, 1658, 715, 11662, 22235, 22245, 13478, 199, 23376, 901, 2759, 21459, 4078, 49, 2379, 6566, 13812, 4346, 6858, 13969, 14963, 1717, 6246, 14947, 15028, 2274, 7432, 14626, 32, 782, 2262, 3814, 10655, 10912, 131, 7437, 14523, 18358, 24174, 1408, 2453, 12394, 20401, 1535, 3051, 9136, 13770, 18625, 24368, 106, 2128, 2829, 8100, 26933, 1024, 11905, 13074, 3, 69, 294, 375, 5133, 16445, 60, 86, 1718, 15762};
namespace sub10{
bitset<lim>cur;
vector<int>solve(){
vector<int>s = {};
vector<pair<int, int>>xy;
cur.reset();
for(int& ci : M30000){
for(int& j : s){
if(ci + j < m && !cur[ci + j]){
xy.push_back(make_pair(min(ci, j), max(ci, j)));
cur[ci + j] = true;
}
}
s.push_back(ci);
}
vector<int>ans(m, 1);
for(auto& [x, y] : xy){
ans[x + y] = y - x;
}
return ans;
}
}
namespace sub11{
vector<int>solve(){
m = 30000;
vector<int>ans_10 = sub10::solve(), ans = ans_10;
for(int z = 0; z < 2; z++){
for(int& i : ans_10){
ans.push_back(i);
}
}
return ans;
}
}
namespace sub12{
bitset<lim>cur;
vector<int>solve(){
cur.reset();
vector<int>s = {0};
vector<pair<int, int>>xy;
while(true){
int ci, best = 0;
for(int i = s.back() + 1; i < s.back() + 300; i++){
int cnt = 0;
for(int& j : s){
if(i + j < m && !cur[i + j]){
cnt++;
}
}
if(maximize(best, cnt)){
ci = i;
}
}
if(best == 0){
break;
}
for(int& j : s){
if(ci + j < m && !cur[ci + j]){
xy.push_back(make_pair(min(ci, j), max(ci, j)));
cur[ci + j] = true;
}
}
s.push_back(ci);
}
vector<int>ans(m, 1);
for(auto& [x, y] : xy){
ans[x + y] = y - x;
}
return ans;
}
}
vector<int>solve(int _m, int _k){
m = _m;
if(m == 20){
return sub7::solve();
}
if(m <= 5000){
return sub89::solve();
}
if(m == 30000){
return sub10::solve();
}
if(m == 100000){
return sub11::solve();
}
return sub12::solve();
}
}
vector<int>construct_range(int m, int k){
return sub789101112::solve(m, k);
}
