OIG XV - plu

// https://szkopul.edu.pl/problemset/problem/DJN8oaDlV5EfddZP8aBWyA_t/site/?key=statement
// XV OIJ (2 etap)

#include <iostream>
#include <limits.h>
#include <map>
#include <vector>

constexpr int sizik = 4 * 100 * 1000 + 23;

int wieze[sizik];

int n;

int temp1[sizik], temp2[sizik];

bool check(int s) {
    if (s <= 0) {
        return true;
    }

    if (2 * s + 1 > n) {
        return false;
    }

    if (s + 1 > n - s) {
        return false;
    }

    for (int i = 1; i <= n; i++) {
        temp1[i] = temp1[i - 1] + (wieze[i] >= s + 1);
    }

    for (int i = s + 1; i <= n - s; i++) {
        if (wieze[i] >= 2 * s + 1) {
            if (temp1[i + s] - temp1[i - s - 1] == 2 * s + 1) {
                return true;
            }
        }
    }

    return false;
}

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

    std::cin >> n;

    for (int i = 1; i <= n; i++) {
        std::cin >> wieze[i];
    }

    int p = 0;
    int k = sizik;

    int s = 0;

    while (p < k) {
        s = (p + k + 1) / 2;

        if (check(s)) {
            p = s;
        } else {
            k = s - 1;
        }
    }

    std::cout << k << '\n';

    return 0;
}