# The isBadVersion API is already defined for you.

# @param version, an integer

# @return a bool

# def isBadVersion(version):

class Solution(object):

    def firstBadVersion(self, n):

        """

        :type n: int

        :rtype: int

        """

        if n < 1:

            return -1

        left=1

        right=n

        while left + 1 < right:

            mid=(left+right)/2

            bolBad = isBadVersion(mid)

            if bolBad:

                right=mid

            else:

                left=mid

        if isBadVersion(left):

            return left

        elif isBadVersion(right):

            return right

        return -1