Circular Array Shortest Path Sum over Multiple Queries

You are given a cycle with N nodes labeled 0..N-1 and an array dist of length N, where dist[i] is the clockwise distance from node i to node (i+1) mod N. There are Q queries. Each query provides two nodes a and b (0 <= a,b < N). For each query, compute the shortest distance from a to b along the cycle (either clockwise or counterclockwise, take the minimum). Sum the shortest distances over all queries and output the total. Input (stdin) Line 1: two integers N Q Line 2: N integers dist[0..N-1] Next Q lines: two integers a b Output (stdout) One integer: the sum of shortest distances over all queries. Constraints 1 <= N <= 2*10^5 1 <= Q <= 2*10^5 1 <= dist[i] <= 10^9 Use 64-bit integer for the sum. Example Input 4 3 1 2 3 4 0 1 0 2 3 1 Output 6