There are `n` gas stations along a circular route, where the amount of gas at the `i-th` station is `gas[i]`.
You have a car with an unlimited gas tank and it costs `cost[i]` of gas to travel from the `i-th` station to its next `(i + 1)-th` station. You begin the journey with an empty tank at one of the gas stations.
Given two integer arrays `gas` and `cost`, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return `-1`. If there exists a solution, it is guaranteed to be unique.
### Constraints
- `n == gas.length == cost.length`
- `1 <= n <= 10^5`
- `0 <= gas[i], cost[i] <= 10^4`
### Input Format
- Line 1: Space-separated integers representing `gas`.
- Line 2: Space-separated integers representing `cost`.
### Output Format
Print the starting station index, or -1.
Sample Cases
Example 1Sample Case
Input: 1 2 3 4 5
3 4 5 1 2
Output: 3
Example 2Sample Case
Input: 2 3 4
3 4 3
Output: -1
Example 3Sample Case
Input: 1
3
Output: -1
Example 4Sample Case
Input: 1 2 3 4 5
1 2 3 4 5
Output: 0
Constraints
Runtime Limit: 2000 ms per test batch
Memory Limit: 256 MB
Standard I/O stream reading
Official submissions are evaluated against hidden test cases on the server to verify time & memory complexity.