/**
 * // This is the ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * class ArrayReader {
 *   public:
 *     int get(int index);
 * };
 */

class Solution {
public:
    int search(const ArrayReader& reader, int target) {
        int l = 0;
        int r = 1;
        int mid;
        int num;

        // Find right most point which covered by 2^right-1 and 2^right
        while(reader.get(r) != INT_MAX){
            l = r;
            r = r << 1;
        }

        // Find right most point
        while(l <= r){
            mid = l + (r - l) / 2;
            if(reader.get(mid) == INT_MAX){
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        r = l;
        l = 0;

        while(l <= r){
            mid = l + (r - l) / 2;
            num = reader.get(mid);
            if(num == target) return mid;
            else if(num > target) r = mid - 1;
            else l = mid + 1;
        }
        
        return -1;
    }
};