Бинпоиск по ответу выдаёт WA на единицу: проблема с границами и предикатом

90% off-by-one в бинпоиске лечатся одним дисциплинированным шаблоном. Зафиксируй инвариант и не отступай от него.

Шаблон «минимальный true» (предикат false...false true...true, ищем первую истину):

int lo = LO, hi = HI;       // ответ гарантированно в [lo, hi], check(hi) == true
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;   // округление ВНИЗ
    if (check(mid)) hi = mid;       // mid годится — может быть ответом, не отбрасываем
    else lo = mid + 1;              // mid не годится — отбрасываем строго
}
// lo == hi — искомый минимальный true

Шаблон «максимальный true» (предикат true...true false...false):

while (lo < hi) {
    int mid = lo + (hi - lo + 1) / 2; // округление ВВЕРХ — обязательно!
    if (check(mid)) lo = mid;
    else hi = mid - 1;
}

Чеклист отладки off-by-one:

1. Округление mid. В «минимальном true» — вниз. В «максимальном true» — вверх (+1). Перепутал — бесконечный цикл или off-by-one.
2. Куда включается mid. Если check(mid) истинно и mid — кандидат, нельзя писать hi = mid - 1 (потеряешь ответ). Должно быть hi = mid.
3. Начальные границы. Проверь, что искомое значение внутри [lo, hi] и что check на крайних значениях ведёт себя как ждёшь (граница «всегда true»/«всегда false» включена).
4. Сам предикат. Часто WA не в поиске, а в check: проверь её на тех самых LO и HI вручную.

Отлаживай так: распечатай check(x) для всех x в маленьком тесте — должна быть ровно одна точка перехода. Если переходов несколько — предикат немонотонен, бинпоиск неприменим в принципе.