#include <bits/stdc++.h>

using ll = long long;
using namespace std;

void I_love_feblokas();

int32_t main() {
    int32_t tc = 1;
    cin >> tc;
    while (tc-->0) {
        I_love_feblokas();
    }
    return 0;
}

void I_love_feblokas() {
    int32_t ans = 0, cnt = 0;
    int n;
    cin >> n;
    string s;
    cin >> s;
    for (auto &c : s) {
        if (c == '*') {
            cnt = 0;
        } else {
            cnt++;
        }
        ans = max(ans, (cnt + 1) / 2);
    }
    cout << ans << '\n';
    return;
}

~~~~~

include <bits/stdc++.h>

using ll = long long; using namespace std;

void I_love_feblokas();

int32_t main() { int32_t tc = 1; cin >> tc; while (tc-- > 0) { I_love_feblokas(); } return 0; }

void I_love_feblokas() { int n; cin >> n; vector a(n); for (auto &x : a) cin >> x; ll cur = 0; bool ok = true; for (ll i = 0; i < n; ++i) { cur += a[i]; ll need = (i + 1) * (i + 2) / 2; if (cur < need) { ok = false; } } if (ok) { cout << "YES\n"; } else { cout << "NO\n"; } }~~~~~

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

void I_love_feblokas();

int32_t main() {
    int32_t tc = 1;
    cin >> tc;
    while (tc-- > 0) {
        I_love_feblokas();
    }
    return 0;
}

void I_love_feblokas() {
    int n, x, y;
    cin >> n >> x >> y;
    vector<int> p(n);
    for (auto &val : p) cin >> val;
    
    int g = gcd(x, y);
    bool ok = true;
    
    for (int i = 0; i < n; ++i) {
        if ((p[i] % g) != ((i + 1) % g)) {
            ok = false;
            break;
        }
    }
    
    if (ok) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

void I_love_feblokas();

int32_t main() {
    int32_t tc = 1;
    cin >> tc;
    while (tc-->0) {
        I_love_feblokas();
    }
    return 0;
}

void I_love_feblokas() {
    int n, m;
    ll ans = 0;
    cin >> n >> m;
    vector<ll> a(n), b(m);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    b.push_back(0);
    sort(b.begin(), b.end());
    vector<ll> pref(n + 1);
    for (ll i = 0; i < n; ++i) {
        pref[i + 1] = pref[i] + a[i];
    }
    for (ll i = 1; i < b.size(); ++i) {
        ans += abs(pref[b[i]] - pref[b[i - 1]]);
    }
    ans += pref[n] - pref[b.back()];
    cout << ans << '\n';
    return;
}

~~~~~

include <bits/stdc++.h>

using namespace std;

void solve() { int n, q; cin >> n >> q; string s; cin >> s; vector pref(n, 0); for (int i = 0; i < n — 1; ++i) { pref[i + 1] = pref[i] + (s[i] == s[i + 1] ? 1 : 0); } for (int i = 0; i < q; ++i) { int l, r, k; cin >> l >> r >> k; if (l == r) { cout << "YES\n"; continue; } int c = pref[r — 1] — pref[l — 1]; int needed = (c + 1) / 2; if (needed <= k) cout << "YES\n"; else cout << "NO\n"; } }

int main() { int t; cin >> t; while (t--) solve(); return 0; }~~~~~

~~~~~

include <bits/stdc++.h>

using ll = long long; using namespace std;

vector<vector> g; vector leaf; bool ok;

void I_love_feblokas(); pair<int, int> dfs(int u, int p);

int32_t main() { int32_t tc = 1; cin >> tc; while (tc-- > 0) { I_love_feblokas(); } return 0; }

pair<int, int> dfs(int u, int p) { if (!ok) return {0, 0}; if (leaf[u] != 0) { for (int v : g[u]) { if (v != p) { ok = false; return {0, 0}; } } return {leaf[u], leaf[u]}; } vector<pair<int, int>> segs; for (int v : g[u]) { if (v != p) { segs.push_back(dfs(v, u)); if (!ok) return {0, 0}; } } if (segs.empty()) { ok = false; return {0, 0}; } vector<pair<int, int>> sorted_segs = segs; sort(sorted_segs.begin(), sorted_segs.end()); for (size_t i = 0; i < sorted_segs.size() — 1; ++i) { if (sorted_segs[i].second + 1 != sorted_segs[i + 1].first) { ok = false; return {0, 0}; } } int start_pos = -1; for (size_t i = 0; i < segs.size(); ++i) { if (segs[i] == sorted_segs[0]) { start_pos = i; break; } } if (start_pos == -1) { ok = false; return {0, 0}; } for (size_t i = 0; i < segs.size(); ++i) { if (segs[(start_pos + i) % segs.size()] != sorted_segs[i]) { ok = false; return {0, 0}; } } return {sorted_segs[0].first, sorted_segs.back().second}; }

void I_love_feblokas() { int n; cin >> n; g.assign(n + 1, vector()); leaf.assign(n + 1, 0); ok = true; for (int i = 2; i <= n; ++i) { int p; cin >> p; g[p].push_back(i); g[i].push_back(p); } int k = 0; for (int i = 1; i <= n; ++i) { cin >> leaf[i]; k = max(k, leaf[i]); } if (n == 1) { cout << "YES\n"; return; } pair<int, int> res = dfs(1, -1); if (ok && res.first == 1 && res.second == k) { cout << "YES\n"; } else { cout << "NO\n"; } }~~~~~

~~~~~

include <bits/stdc++.h>

using namespace std; using ll = long long;

struct Fenwick { int n; vector t;

Fenwick(int n) : n(n), t(n + 1, 0ll) {}

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

void upd(int pos, ll val) {
    for (; pos <= n; pos += f(pos)) t[pos] = max(t[pos], val);
}

ll get(int pos) {
    ll ans = 0;
    for (; pos > 0; pos -= f(pos)) ans = max(ans, t[pos]);
    return ans;
}

};

void I_love_feblokas() { int n; cin >> n; vector a(n + 1); for (int i = 1; i <= n; ++i) { cin >> a[i]; } Fenwick t(n); vector<vector<pair<int, ll>>> ev(n + 1); ll ans = 0; for (int i = 1; i <= n; ++i) { for (auto& ev : ev[i]) { t.upd(ev.first, ev.second); } int lim = i — a[i] — 1; ll mx = 0; if (lim > 0) { mx = t.get(min(n, lim)); } ll dp_i = a[i] + mx; ans = max(ans, dp_i); ll act = i + a[i] + 1; if (act <= n) { ev[act].push_back({i, dp_i}); } } cout << ans << "\n"; }

int main() { int t; cin >> t ; while (t--) { I_love_feblokas(); } return 0; }~~~~~