Shortest Path Between Circular Drone Hubs

Problem: Shortest Path Between Circular Drone Hubs There are n drone hubs numbered from 0 to n - 1, arranged in a circle in clockwise order. You are given an array distance, where distance[i] is the distance from hub i to its adjacent hub (i + 1) % n in the clockwise direction. You are also given q queries. Each query contains two hubs: start and destination. For each query, return the shortest distance from start to destination. Since the hubs form a circle, there are two possible routes: Move clockwise; Move counterclockwise. Output the shortest distance for each query. Input Format n distance0 distance1 ... distance n-1 q start1 destination1 start2 destination2 ... startq destinationq Output Format Print q lines. Each line contains one integer, the shortest distance for the corresponding query. Constraints 2 <= n <= 200000 1 <= distance[i] <= 10^9 1 <= q <= 200000 0 <= start, destination < n The answer may exceed the 32-bit integer range, so use 64-bit integers. Example Input 4 1 2 3 4 3 0 1 0 2 3 1 Output 1 3 5 Explanation 0 -> 1: clockwise distance is 1, counterclockwise distance is 2 + 3 + 4 = 9, shortest is 1. 0 -> 2: clockwise distance is 1 + 2 = 3, counterclockwise distance is 3 + 4 = 7, shortest is 3. 3 -> 1: clockwise distance is 4 + 1 = 5, counterclockwise distance is 2 + 3 = 5, shortest is 5. Example Input 4 1 2 3 4 3 0 1 0 2 3 1 Output 1 3 5