You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one.

For this problem, isBad(version) returns 1 if version is bad, 0 if good. Find the first bad version using minimum API calls.

Example 1:

Input: n=5, bad=4
Output: 4

Example 2:

Input: n=1, bad=1
Output: 1

Input format: First line: n. Second line: bad (the first bad version).

Output format: The first bad version number.