556. Delivery and Rahul
0
Medium
Rahul works as a delivery driver and needs to deliver 'n' packages to 'n' different cities. The cities are arranged in a circular route, and Rahul must pay a toll tax to enter each city. However, Rahul has no money and relies on tips from the cities to cover the tolls. He can start from any city. Your task is to determine the starting city from which Rahul can successfully deliver all the packages.
Note: If Rahul is at the (i)th city, he needs to pay the toll tax (toll[i]) to travel from the (i)th city to the (i+1)th city. Rahul always travels in a clockwise direction. If a solution exists, it is unique. If no solution exists, print -1.
Input Format
The first line contains an integer 'n' representing the number of cities.
The second line contains 'n' space-separated integers (tip[0], tip[1], ..., tip[n-1]) representing the tips Rahul receives from each city.
The third line contains 'n' space-separated integers (toll[0], toll[1], ..., toll[n-1]) representing the toll tax of each city.
Output Format
Print a single integer representing the index of the city from which Rahul should start his journey.
Example
Input
5
1 2 3 4 5
3 4 5 1 2
Output
3
Constraints
0 <= n <= 1e5
0 <= tip[i] , toll[i] <=1e9
0 <= tip[i] , toll[i] <=1e9
Loading...
View Submissions
Console