Gas Stations

There are n gas stations arranged in a circle, numbered 0 to n - 1. You have a car with an unlimited fuel tank, starting empty. You are given two integer arrays gas and cost of length n: gas[i] is the amount of fuel available at station i, and cost[i] is the fuel required to travel from station i to the next station (i + 1) % n.

You begin your journey at some station with an empty tank. Return the index of the starting station from which you can travel around the entire circuit exactly once without running out of fuel at any point. If no such starting station exists, return -1. It is guaranteed that if a solution exists, it is unique.

Example 1

Input: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Output: 3
Explanation: Starting at station 3: tank = 0 + 4 - 1 = 3, then at
station 4: 3 + 5 - 2 = 6, then at station 0: 6 + 1 - 3 = 4, then
at station 1: 4 + 2 - 4 = 2, then at station 2: 2 + 3 - 5 = 0.
You made it back to station 3 with an empty tank, so it works.

Example 2

Input: gas = [2, 3, 4], cost = [3, 4, 3]
Output: -1
Explanation: The total gas (9) is less than the total cost (10),
so completing the circuit from any starting point is impossible.

Constraints

• n == gas.length == cost.length
• 1 <= n <= 10^5
• 0 <= gas[i], cost[i] <= 10^4