The Doubling Explorer: Find Target in an Infinite Sorted Array

In the realm beyond Prime City's borders, the Doubling Explorer faces a truly infinite sorted array ÔÇö a mathematical construct where every index has a value given by a known formula. The Explorer must find the smallest index i where array[i] >= T. "The infinite array is defined by a function f(i) = a * i + b for i >= 0," the Explorer explains. "Use exponential search to find the range, then binary search for the exact position." Given integers a, b (defining the infinite sorted array f(i) = a*i + b for i >= 0, where a > 0) and a target T, find the smallest non-negative index i such that a*i + b >= T. If T <= b, the answer is 0. Constraints: 1 <= a <= 10^9, -10^9 <= b <= 10^9, -10^9 <= T <= 10^18 Input: 2 1 10 Output: 5 Input: 1 0 5 Output: 5