Given a binary string S (a string consisting only of ‘0’ and ‘1’s) and a positive integer N, return true if and only if for every integer X from 1 to N, the binary representation of X is a substring of S.

Example 1:

Input: S = "0110", N = 3
Output: true
Example 2:

Input: S = "0110", N = 4
Output: false

Note:

1 <= S.length <= 1000
1 <= N <= 10^9

class Solution {
public:

    string to_str(int N) {
        string num = "";
        while(N) {
            int tmp = N % 2;
            N /= 2;
            num += tmp + '0';
        }
        reverse(num.begin(), num.end());
        return num;
    }
    bool queryString(string S, int N) {
        for(int i = 1; i <= N; i++) {
            if(S.find(to_str(i)) == -1)) 
                return false;
        }
        return true;
    }
};

/*
--------------------
h[N]-牛高
ans[N]-记录答案
tr[N]-线段树存储
--------------------
int lowbit(int x);
void add(int x, int c);
int sum(int x);
---------------------
1.从剩余的数中找到第k小的数~找到一个最大的x使得k==sum(x)
2.删除某个数
*/

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int n;
int h[N], res[N], tr[N];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int c) {
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += c; 
}

int sum(int x) {
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}


int main() {
    cin >> n;

    for(int i = 2; i <= n; i++) cin >> h[i];

    for(int i = 1; i <= n ;i++) tr[i] = lowbit(i);

    for(int i = n; i; i--) {
        int k = h[i] + 1;
        int l = 1, r = n;
        while(l < r) {
            int mid = l + r >> 1;
            if(sum(mid) >= k) r = mid;
            else l = mid + 1;
        }
        res[i] = r;
        add(r, -1);
    }

    for(int i = 1; i <= n; i++) cout << res[i] << endl;

    return 0;
}

/*
--------------------
h[N]-牛高
ans[N]-记录答案
tr[N]-线段树存储
--------------------
int lowbit(int x);
void add(int x, int c);
int sum(int x);
---------------------
1.从剩余的数中找到第k小的数~找到一个最大的x使得k==sum(x)
2.删除某个数
*/

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int n;
int h[N], res[N], tr[N];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int c) {
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += c; 
}

int sum(int x) {
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}


int main() {
    cin >> n;

    for(int i = 2; i <= n; i++) cin >> h[i];

    for(int i = 1; i <= n ;i++) tr[i] = lowbit(i);

    for(int i = n; i; i--) {
        int k = h[i] + 1;
        int l = 1, r = n;
        while(l < r) {
            int mid = l + r >> 1;
            if(sum(mid) >= k) r = mid;
            else l = mid + 1;
        }
        res[i] = r;
        add(r, -1);
    }

    for(int i = 1; i <= n; i++) cout << res[i] << endl;

    return 0;
}

/*
-----------
tr1[i]-bi的前缀和数组
tr2[i]-i*bi的前缀和数组
a[1~x] == (x+1) * b[1~x](即tr1[x]) - tr2[i]
-----------
int lowbit(int x);
void add(LL tr[], int x, LL c);
LL sum(LL tr[], int x);
LL prefix_sum(int x);
*/
#include<iostream>
#include<cstring>
#include<algorithm>

typedef long long LL;

using namespace std;

const int N = 1e5+10;
int n, m;
LL a[N], tr1[N], tr2[N];

int lowbit(int x) {
    return x & -x;
}

void add(LL tr[], int x, LL c) {
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

LL sum(LL tr[], int x) {
    LL res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

LL prefix_sum(int x) {
    return sum(tr1, x) * (x + 1) - sum(tr2, x);
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) 
        cin >> a[i];

    for(int i = 1; i <= n; i++) {
        int b = a[i] - a[i-1];
        add(tr1, i, b);
        add(tr2, i, (LL)b*i);
    }
    while(m--) {
        char op[2];
        int l, r, d;

        cin >> op;
        if(op[0] == 'Q') {
            cin >> l >> r;
            cout << prefix_sum(r) - prefix_sum(l-1) << endl;
        } else {
            cin >> l >> r >> d;
            add(tr1, l, d), add(tr2, l, l * d);
            add(tr1, r+1, -d), add(tr2, r+1, (r+1) * -d);
        }
    }
    return 0;
}

// 这破题我居然写了半小时，吐了
// class Solution {
// public:
//     int isPrefixOfWord(string sentence, string searchWord) {
//     // typedef pair<string, int> sent[110];
//     int res = -1,cnt = 1;;
//     for(int i = 0; i < sentence.size(); i++) {
//         string tmp;
//         if(sentence[i] != ' ') continue;
//         else if(sentence[i] == ' ' || i == sentence.size()){
//             tmp = sentence.substr(0, i-1);
//             sentence = sentence.substr(i+1);
//             cout << "---" << cnt << ' ' << tmp << ' ' << sentence << endl;
//             for(int i = 0; i < searchWord.size(); i++) {
//                 if(searchWord[i] != tmp[i]) {
//                     break;
//                 }
//                 if(searchWord[i] == tmp[i] && i == searchWord.size() - 1) res = cnt;
//             } 
//             cnt++;
//             // sent[cnt] = make_pair(tmp, cnt++);
//             // sent[cnt].first = tmp;
//             // sent[cnt].second = cnt++; 
//         } 
//     }
//     // for(int i = 1; i <= cnt; i++) {
//     //     for(int j = 0; j < searchWord.size(); j++) {
//     //         if(sent[i].first[j] != searchWord[j]) continue;
//     //         if(j == searchWord.size() - 1) res = sent[i].second;
//     //     }
//     // } 
//     // cout << res << endl;
//     return res;
// }
// };
class Solution {
public:
int isPrefixOfWord(string sentence, string searchWord) {
    int res = -1,cnt = 1;
    for(int i = 0; i < sentence.size(); i++) {
        string tmp;
        if(sentence[i] == ' '){
            tmp = sentence.substr(0, i);
            sentence = sentence.substr(i+1);
            // cout << "---" << cnt << "---" << tmp << "---" << sentence << endl;

            for(int i = 0; i < searchWord.size(); i++) {
                if(searchWord[i] != tmp[i]) {
                    break;
                }
                if(searchWord[i] == tmp[i] && i == searchWord.size() - 1) return cnt;

            } 

            for(int i = 0; i < searchWord.size(); i++) {
                if(sentence[i] != searchWord[i]) {
                    break;
                }
                if(sentence[i] == searchWord[i] && i == searchWord.size() - 1) return cnt+1;
            }
            cnt++;
            i = 0;
        } 
    }
    return res;
}
};

]

// 这破题写了我半个小时，我吐了
// class Solution {
// public:
//     int isPrefixOfWord(string sentence, string searchWord) {
//     // typedef pair<string, int> sent[110];
//     int res = -1,cnt = 1;;
//     for(int i = 0; i < sentence.size(); i++) {
//         string tmp;
//         if(sentence[i] != ' ') continue;
//         else if(sentence[i] == ' ' || i == sentence.size()){
//             tmp = sentence.substr(0, i-1);
//             sentence = sentence.substr(i+1);
//             cout << "---" << cnt << ' ' << tmp << ' ' << sentence << endl;
//             for(int i = 0; i < searchWord.size(); i++) {
//                 if(searchWord[i] != tmp[i]) {
//                     break;
//                 }
//                 if(searchWord[i] == tmp[i] && i == searchWord.size() - 1) res = cnt;
//             } 
//             cnt++;
//             // sent[cnt] = make_pair(tmp, cnt++);
//             // sent[cnt].first = tmp;
//             // sent[cnt].second = cnt++; 
//         } 
//     }
//     // for(int i = 1; i <= cnt; i++) {
//     //     for(int j = 0; j < searchWord.size(); j++) {
//     //         if(sent[i].first[j] != searchWord[j]) continue;
//     //         if(j == searchWord.size() - 1) res = sent[i].second;
//     //     }
//     // } 
//     // cout << res << endl;
//     return res;
// }
// };
class Solution {
public:
int isPrefixOfWord(string sentence, string searchWord) {
    int res = -1,cnt = 1;
    for(int i = 0; i < sentence.size(); i++) {
        string tmp;
        if(sentence[i] == ' '){
            tmp = sentence.substr(0, i);
            sentence = sentence.substr(i+1);
            // cout << "---" << cnt << "---" << tmp << "---" << sentence << endl;

            for(int i = 0; i < searchWord.size(); i++) {
                if(searchWord[i] != tmp[i]) {
                    break;
                }
                if(searchWord[i] == tmp[i] && i == searchWord.size() - 1) return cnt;

            } 

            for(int i = 0; i < searchWord.size(); i++) {
                if(sentence[i] != searchWord[i]) {
                    break;
                }
                if(sentence[i] == searchWord[i] && i == searchWord.size() - 1) return cnt+1;
            }
            cnt++;
            i = 0;
        } 
    }
    return res;
}
};

#include <iostream>

const int N = 1e6+10;

using namespace std;

int n, m;
long long w[N], s[N];

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> w[i];
    for(int i = 1; i <= n; i++) s[i] = s[i-1] + w[i];

    long long res = 0;
    for(int i = m; i <= n; i++) 
        res = max(res, s[i] - s[i - m - 1]);
    cout << res << endl;
    return 0;
}

#include <iostream>

const int N = 1e6+10;

using namespace std;

int n, m;
long long w[N], s[N];

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> w[i];
    for(int i = 1; i <= n; i++) s[i] = s[i-1] + w[i];

    long long res = 0;
    for(int i = m; i <= n; i++) 
        res = max(res, s[i] - s[i - m - 1]);
    cout << res << endl;
    return 0;
}