|
ong[MAXN], mxblock, num[MAXN];
LL Solve1(int l, int r) {
for(int i = 1; i < l; i++) num[a[i]]++;
LL ret = 0;
for(int j = l; j <= r; j++)
for(int k = j + 1; k <= r; k++)
if(2 * a[j] - a[k] >= 0) ret += num[2 * a[j] - a[k]];
for(int i = 1; i < l; i++) num[a[i]]--;
for(int i = N; i > r; i--) num[a[i]]++;
for(int j = r; j >= l; j--)
for(int k = j - 1; k >= l; k--)
if(2 * a[j] - a[k] >= 0) ret += num[2 * a[j] - a[k]];
for(int i = N; i > r; i--) num[a[i]]--;
for(int j = l; j <= r; j++) {
for(int i = j - 1; i >= l; i--) num[a[i]]++;
for(int k = j + 1; k <= r; k++)
if(2 * a[j] - a[k] >= 0) ret += num[2 * a[j] - a[k]];
for(int i = j - 1; i >= l; i--) num[a[i]]--;
}
return ret;
}
int ta[MAXN], tb[MAXN], Lim;
LL Solve2(int l, int r) {
memset(ta, 0, sizeof(ta));
memset(tb, 0, sizeof(tb));
for(int i = l - 1; i >= 1; i--) ta[a[i]]++;
for(int i = r + 1; i <= N; i++) tb[a[i]]++;
Mul(ta, tb, mx, mx); LL ret = 0;
for(int i = l; i <= r; i++) ret += tb[2 * a[i]];
return ret;
}
signed main() {
//freopen("a.in", "r", stdin);
N = read(); block = sqrt(8 * N * log2(N));
memset(ll, 0x3f, sizeof(ll));
for(int i = 1; i <= N; i++) {
belong[i] = (i - 1) / block + 1; chmax(mxblock, belong[i]);
chmin(ll[belong[i]], i);
chmax(rr[belong[i]], i);
a[i] = read(), chmax(mx, a[i]);
}
Lim = GetLen(mx); Init(4 * Lim);
LL ans = 0;
for(int i = 1; i <= mxblock; i++) {
ans += Solve1(ll[i], rr[i]);
ans += Solve2(ll[i], rr[i]);
}
cout << ans;
return 0;
}
/*
7
7 0 4 7 0 8 8
*/
|