def isBadVersion(version: int) -> bool:
    raise NotImplementedError


class Solution:
    def firstBadVersion(self, n: int) -> int:
        lo, hi = 1, n
        while lo < hi:
            check = (hi + lo) // 2
            if isBadVersion(check):
                hi = check
            else:
                lo = check + 1
        return lo