#include <cstdint>
#include <utility>
#include <vector>

#include "secret.h"

template <typename F>
class y_combinator {

private:

    F f;

public:

    explicit y_combinator(F&& f) : f(f) {}

    template <typename... Args>
    decltype(auto) operator()(Args&&... args) const {

        return f(*this, std::forward<Args>(args)...);

    }

};

template <typename F>
y_combinator(F) -> y_combinator<F>;

std::vector<std::vector<std::int32_t>> tbl;

void Init(int n, int a[]) {

    tbl.resize(n, std::vector<std::int32_t>(n));

    for (std::int32_t i = 0; i < n; ++i) {
        tbl[i][i] = a[i];
    }

    y_combinator(
        [&](auto self, std::int32_t idx_l, std::int32_t idx_r) -> void {
            const std::int32_t idx_m = (idx_l + idx_r) / 2;
            for (std::int32_t i = idx_m - 2; i >= idx_l; --i) {
                tbl[i][idx_m - 1] = Secret(a[i], tbl[i + 1][idx_m - 1]);
            }
            for (std::int32_t i = idx_m + 1; i < idx_r; ++i) {
                tbl[idx_m][i] = Secret(tbl[idx_m][i - 1], a[i]);
            }
            if (idx_m - idx_l >= 2) {
                self(idx_l, idx_m);
            }
            if (idx_r - idx_m >= 2) {
                self(idx_m, idx_r);
            }
        }
    )(0, n);

}

int Query(int l, int r) {

    std::int32_t idx_l = 0;
    std::int32_t idx_r = std::size(tbl);

    while (idx_r - idx_l > 1) {
        const std::int32_t idx_m = (idx_l + idx_r) / 2;
        if (l < idx_m && r >= idx_m) {
            return Secret(tbl[l][idx_m - 1], tbl[idx_m][r]);
        }
        if (l < idx_m) {
            idx_r = idx_m;
        } else {
            idx_l = idx_m;
        }
    }

    return tbl[idx_l][idx_r - 1];

}