#include <stdbool.h>
bool isBadVersion(int version);

int firstBadVersion(int n) {
    if (isBadVersion(n) && !isBadVersion(n-1))
        return n;

    int left = 0;
    int right = n - 1;
    int index;

    while (left <= right) {
        index = left + (right - left) / 2;
        int isBad = isBadVersion(index);
        if (isBad && !isBadVersion(index - 1)) {
            return index;
        }
        if (!isBad)
            left = index + 1;
        else
            right = index - 1;
    }
    return -1;
}
