#include "monede.h"

constexpr int maxn = 1e6 + 10;

int n;
Raport v[2 * maxn];

void init(int N, const Raport p[]) {
    n = N;
    for (int i = 0; i < n; ++i)
        v[i + n] = Raport(1, 1) - Raport(2, 1) * p[i];

    for (int i = n - 1; i > 0; --i)
        v[i] = v[2 * i] * v[2 * i + 1];
}

Raport solve(int a, int b) {
    Raport r(1, 1);

    for (a += n, b += n + 1; a < b; a /= 2, b /= 2) {
        if (a % 2)
            r *= v[a++];
        if (b % 2)
            r *= v[--b];
    }
    return (Raport(1, 1) - r) * Raport(1, 2);
}
