OIG XV - ant

// https://szkopul.edu.pl/problemset/problem/c-iPsg6lceV8Nkkk9Zw1s1iN/site/?key=statement

#include <bits/stdc++.h>

using namespace std;

#define int long long

constexpr int sizik = 1507;

#define ar std::array
#define pr std::pair
#define vec std::vector

typedef vec<vec<int>> _kra;

int dp[sizik][sizik];
int dp1[sizik][sizik];
int r[sizik];

void solve() {
    int n, m;
    std::cin >> n >> m;

    std::set<int> s;
    std::vector<int> v;
    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;

        r[a]++;
        s.insert(a);
    }

    v.push_back(0);
    for (const auto& a : s) {
        v.push_back(a);
    }
    int vn = (int)v.size();

    int ans = 0;

    dp[0][0] = 1;
    for (int i = 0; i < vn; i++) {
        dp1[0][i] = 1;
    }

    for (int i = 1; i < vn; i++) {
        int k = i;
        for (int j = 0; j < i; j++) {
            // for (int k = 0; v[j] + v[k] <= v[i]; k++) {
            //     dp[i][j] += dp[j][k];
            //     ans += dp[j][k];
            // }
            while (k >= 0 && v[j] + v[k] > v[i])
                k--;

            if (k >= 0) {
                // std::cout << i << " " << j << " " << k << " | ";
                // std::cout << v[i] << " " << v[j] << " " << v[k] << '\n';

                dp[i][j] += dp1[j][k];
                ans += dp1[j][k];
            }
        }

        if (r[v[i]] > 1) {
            dp[i][i] = 1;
            ans++;
        }

        dp1[i][0] = dp[i][0];
        for (int j = 1; j < vn; j++) {
            dp1[i][j] = dp1[i][j - 1] + dp[i][j];
        }
    }

    // std::cout << "dp \n";
    // for (int j = 0; j < vn; j++) {
    //     for (int i = 0; i < vn; i++) {
    //         std::cout << dp[i][j] << ' ';
    //     }
    //     std::cout << '\n';
    // }

    // std::cout << "dp1 \n";
    // for (int j = 0; j < vn; j++) {
    //     for (int i = 0; i < vn; i++) {
    //         std::cout << dp1[i][j] << ' ';
    //     }
    //     std::cout << '\n';
    // }

    std::cout << ans << '\n';
}

int32_t main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int t = 1;
    // std::cin >> t

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}