#include "monede.h"
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 2e6 + 1;

int nr_jumate[maxn];
// nr_jumate[i] = de cate ori apare 1 / 2 printre primele i numere ?
Raport r[maxn];
// r[i] = produsul primelor i valori de forma (1 - 2p), unde p e o
// probabilitate, ignorand valorile de 1 / 2.

void init(int n, const Raport p[]) {
    nr_jumate[0] = 0;
    r[0] = Raport(1, 1);

    for (int i = 0; i < n; ++i)
        if (p[i] == Raport(1, 2)) {
            nr_jumate[i + 1] = nr_jumate[i] + 1;
            r[i + 1] = r[i];
        } else {
            nr_jumate[i + 1] = nr_jumate[i];
            r[i + 1] = (Raport(1, 1) - Raport(2, 1) * p[i]) * r[i];
        }
}

Raport solve(int x, int y) {
    // Daca avem cel putin un 1 / 2 in interval, returnam 1 / 2, altfel
    // returnam valoarea din descrierea solutiei.
    return nr_jumate[y + 1] > nr_jumate[x]
               ? Raport(1, 2)
               : (Raport(1, 1) - r[y + 1] / r[x]) / Raport(2, 1);
}
