Tam Giác Pháo Hoa

#include<bits/stdc++.h>
 
using namespace std;
using LL = long long;
#define fi first
#define se second
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(a) int(a.size())
void debug_out() {cout << '\n';}
template <typename Head, typename ...Tail>
void debug_out(Head H, Tail ...T){
    cout << H << ' ';
    debug_out(T...);
}
#define debug(...) cout << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
 
const int N = 5 * 1e3 + 11;
LL a[N], b[N], n, ans1, ans2, ans3;

 
 
signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    clock_t start = clock();
 
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];    
    sort(a, a + n);
    for (int i = 0; i < n; ++i) b[i] = a[i] * a[i];

    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int idx = lower_bound(b + j + 1, b + n, b[i] + b[j]) - begin(b);
            ans1 += idx - j - 1;
        }
    }

    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int idx = lower_bound(b + j + 1, b + n, b[i] + b[j]) - begin(b);
            if (idx < n && b[i] + b[j] == b[idx]) ++ans2;
        }
    }

    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int idx1 = upper_bound(b + j + 1, b + n, b[i] + b[j]) - begin(b);
            int idx2 = -1;
            idx2 = lower_bound(a + idx1, a + n, a[i] + a[j]) - begin(a);
            ans3 += idx2 - idx1;
        }
    }

    cout << ans1 << ' ' << ans2 << ' ' << ans3 << '\n'; 
    clock_t end = clock();
    cerr << "Time: " << fixed << setprecision(10) << double (end - start) / double (CLOCKS_PER_SEC) << '\n';
    return 0;
}