std::sort(a, a+n);

#include <iostream>
#include <vector>
using namespace std;

int main() {
    /* 入力受け取り */
    int n, Q;
    cin >> n >> Q;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    
    /* Q 回分のクエリを処理 */
    for (int j = 0; j < Q; ++j) {
        long long x; cin >> x; // 各クエリ x
        
        /* 合計値 */
        long long res = 0;
        
        /* 区間の左端 left で場合分け */
        for (int left = 0; left < n; ++left) {
            long long sum = 0;
            int right = left; // [left, right) の総和が x 以下となる最大の right を求める
            
            /* sum に a[right] を加えても大丈夫なら right を動かす */
            while (right < n && sum + a[right] <= x) {
                sum += a[right];
                ++right;
            }
            
            /* break した状態で right は条件を満たす最大 */
            res += (right - left);
        }
        
        cout << res << endl;
    }
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    /* 入力受け取り */
    int n, Q;
    cin >> n >> Q;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    
    /* Q 回分のクエリを処理 */
    for (int j = 0; j < Q; ++j) {
        long long x; cin >> x; // 各クエリ x
        
        /* 合計値 */
        long long res = 0;
        
        /* 区間の左端 left で場合分け */
        int right = 0;     // 毎回 right を使い回すようにする
        long long sum = 0; // sum も使い回す
        for (int left = 0; left < n; ++left) {
            /* sum に a[right] を加えても大丈夫なら right を動かす */
            while (right < n && sum + a[right] <= x) {
                sum += a[right];
                ++right;
            }
            
            /* break した状態で right は条件を満たす最大 */
            res += (right - left);
            
            /* left をインクリメントする準備 */
            if (right == left) ++right; // right が left に重なったら right も動かす
            else sum -= a[left]; // left のみがインクリメントされるので sum から a[left] を引く
        }
        
        cout << res << endl;
    }
}

int right = 0;     
for (int left = 0; left < n; ++left) {
    while (right < n && (right を 1 個進めたときに条件を満たす)) {
        /* 実際に right を 1 進める */
        // ex: sum += a[right];
        ++right;
    }

    /* break した状態で right は条件を満たす最大なので、何かする */
    // ex: res += (right - left);

    /* left をインクリメントする準備 */
    // ex: if (right == left) ++right;
    // ex: else sum -= a[left];
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    /* クエリ回数 */
    int Q;
    cin >> Q;
    
    for (int query = 0; query < Q; ++query) {
        /* 入力受け取り */
        int n; cin >> n;
        long long x; cin >> x;
        vector<long long> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        
        /* 区間の長さの最小値 */
        int res = n+1; // 上界を入れておく
        
        /* 区間の左端 left で場合分け */
        int right = 0;
        long long sum = 0;
        for (int left = 0; left < n; ++left) {
            /* [left, right) の総和が x 以上となる最小の right を求める */
            while (right < n && sum < x) {
                sum += a[right];
                ++right;
            }
            
            /* 更新 */
            if (sum < x) break; // これ以上 left を進めてもダメ
            res = min(res, right - left);
            
            /* left をインクリメントする準備 */
            if (right == left) ++right; // right が left に重なったら right も動かす
            else sum -= a[left]; // left のみがインクリメントされるので sum から a[left] を引く
        }
        
        /* res = n+1 のときは解なし */
        if (res < n+1) cout << res << endl;
        else cout << 0 << endl;
    }
}

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
using pll = pair<long long, long long>;

// slide min
template<class VAL, class TIME> struct SlideMin {
    const VAL INF = 1LL<<60; // to be set appropriately
    const TIME nul = -1; // to be set appropriately
        
    deque<pair<VAL, TIME> > deq;
    SlideMin()  { }

    // get minimum
    pair<VAL, TIME> get() {
        if (deq.empty()) return make_pair(INF, nul);
        return deq.front();
    }

    // push (v, t), "t is non-decreasing" is necessary
    void push(VAL v, TIME t) {
        while (!deq.empty() && deq.back().first >= v) deq.pop_back();
        deq.emplace_back(v, t);
    }

    // pop "< t", "t it non-decreasing" is necessary
    void pop(TIME t) {
        while (!deq.empty() && deq.front().second < t) deq.pop_front();
    }
};

#include <iostream>
#include <vector>
using namespace std;

int main() {
    /* 入力受け取り */
    int n;
    long long K;
    cin >> n >> K;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    
    /* 0 があったら n をリターン */
    for (int i = 0; i < n; ++i) {
        if (a[i] == 0) {
            cout << n << endl;
            return 0;
        }
    }
    
    /* しゃくとり法 */
    int res = 0;
    int right = 0;
    long long mul = 1;
    for (int left = 0; left < n; ++left) {
        while (right < n && mul * a[right] <= K) {
            mul *= a[right];
            ++right;
        }
        res = max(res, right - left); // 更新
        if (left == right) ++right;
        else mul /= a[left]; // left を除く
    }
    
    cout << res << endl;
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    /* 入力受け取り */
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    
    /* しゃくとり法 */
    long long res = 0;
    int right = 1; // [0, 1) は確実に条件を満たす
    for (int left = 0; left < n; ++left) {
        // right を 1 個進めたものが条件を満たすかどうか
        while (right < n && (right <= left || a[right - 1] < a[right])) {
            ++right;
        }
        res += right - left;
        if (left == right) ++right;
    }
    
    cout << res << endl;
}

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main() {
    /* 入力受け取り */
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    
    /* しゃくとり法 */
    int res = 0;
    int right = 0;
    set<int> member;
    
    for (int left = 0; left < n; ++left) {
        while (right < n && !member.count(a[right])) {
            member.insert(a[right]);
            ++right;
        }
        res = max(res, right - left);
        if (left == right) ++right;
        else {
            member.erase(a[left]); // a[left] を削除
        }
    }
    
    cout << res << endl;
}

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main() {
    /* 入力受け取り */
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    
    /* しゃくとり法 */
    long long res = 0;
    int right = 0;
    int sum = 0; // AND 和
    for (int left = 0; left < n; ++left) {
        while (right < n && (sum ^ a[right]) == (sum + a[right])) {
            sum += a[right];
            ++right;
        }
        res += right - left;
        if (left == right) ++right;
        else {
            sum -= a[left]; // a[left] を削除 (sum ^= a[left] でも OK)
        }
    }
    
    cout << res << endl;
}

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1000000007;
int dp[110000];
int sum[110000];

int main() {
    /* 入力 */
    int N, M;
    cin >> N >> M;
    vector<int> f(N);
    for (int i = 0; i < N; ++i) cin >> f[i], --f[i];
    
    /* しゃくとり法 */
    vector<int> fnum(M, 0); // 区間に種類 i が何個あるか
    vector<int> L(N+1, 0); // 各 i に対するしゃくとり法の区間
    int left = 0;
    for (int right = 0; right < N; ++right) {
        fnum[f[right]]++;
        while (left < right && fnum[f[right]] > 1) {
            --fnum[f[left]];
            ++left;
        }
        L[right+1] = left;
    }
    
    /* 累積和で高速化した DP */
    dp[0] = 1;
    sum[0] = 0; sum[1] = 1;
    for (int i = 1; i <= N; ++i) {
        dp[i] = (sum[i] - sum[L[i]] + MOD) % MOD; // DP
        sum[i+1] = (sum[i] + dp[i]) % MOD; // 累積
    }
    
    cout << dp[N] << endl;
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    /* 入力 */
    int N;
    cin >> N;
    vector<long long> a(N*2); // 環状の数列を扱うときは二週確保はよくやる
    long long total = 0; // バームクーヘン全体のサイズ
    for (int i = 0; i < N; ++i) cin >> a[i], a[i+N] = a[i], total += a[i];
    
    /* 二分探索 */
    long long low = 0, high = 1LL<<60;
    while (high - low > 1) {
        /* 3 ピースとも mid 以上にできるかを判定する */
        long long mid = low + (high - low) / 2;
    
        /* しゃくとり法により、各切れ目から mid 以上になる最小区間がどこまでかを求める */
        vector<int> Next(N, -1);
        vector<long long> Size(N, -1);
        int right = 0;
        long long sum = 0;
        for (int left = 0; left < N; ++left) {
            while (right < N*2 && sum < mid) {
                sum += a[right];
                ++right;
            }
            if (sum >= mid) { // mid 以上なら記録
                Next[left] = right;
                Size[left] = sum;
            }
            if (right == left) ++right;
            else sum -= a[left];
        }
        
        /* check */
        bool ok = false;
        for (int i = 0; i < N; ++i) {
            /* 1 ピース目 */
            int ni = Next[i];
            if (ni == -1) continue;
            if (Size[i] >= total) continue;
            
            /* 2 ピース目 */
            ni %= N;
            int nni = Next[ni];
            if (nni == -1) continue;
            
            // 残りが mid 以上なら OK
            if (total - Size[i] - Size[ni] >= mid) ok = true;
        }
        
        if (!ok) high = mid;
        else low = mid;
    }
    
    cout << low << endl;
}

#include <iostream>
#include <vector>
using namespace std;

/* BIT */
template <class Abel> struct BIT {
    vector<Abel> dat;
    Abel UNITY_SUM = 0;						// to be set
    
    /* [1, n] */
    BIT(int n) { init(n); }
    void init(int n) {
        dat.resize(n + 1);
        for (int i = 0; i < (int)dat.size(); ++i) dat[i] = UNITY_SUM;
    }
    
    /* a is 1-indexed */
    inline void add(int a, Abel x) {
        for (int i = a; i < (int)dat.size(); i += i & -i)
            dat[i] = dat[i] + x;
    }
    
    /* [1, a], a is 1-indexed */
    inline Abel sum(int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i)
            res = res + dat[i];
        return res;
    }
    
    /* [a, b), a and b are 1-indexed */
    inline Abel sum(int a, int b) {
        return sum(b - 1) - sum(a - 1);
    }
};

int main() {
    /* 入力 */
    int N, K;
    long long L;
    cin >> N >> K >> L;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    
    /* 二分探索 */
    int low = 0, high = N;
    while (high - low > 1) {
        /* mid 以下の値が L 個あるかを判定する */
        int mid = low + (high - low) / 2;
        
        /* しゃくとり法で、mid 以下の値が K 個以上あるような区間を数え上げる */
        BIT<int> bit(N+1);
        int right = 0;
        long long num = 0;
        for (int left = 0; left < N; ++left) {
            while (right < N && bit.sum(mid) < K) {
                bit.add(a[right], 1);
                ++right;
            }
            if (bit.sum(mid) < K) break;
            num += N - right + 1;
            bit.add(a[left], -1);
        }
        
        if (num >= L) high = mid;
        else low = mid;
    }
    
    cout << high << endl;
}