{"problem":{"name":"D. Roads (A)","description":{"content":"There are N cities numbered from 1 to N with N roads connecting them. The ith road goes between the two cities i and i + 1 (1 ≤ i < N), and the last road goes between the first and the last city. The ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10140D"},"statements":[{"statement_type":"Markdown","content":"There are N cities numbered from 1 to N with N roads connecting them. The ith road goes between the two cities i and i + 1 (1 ≤ i < N), and the last road goes between the first and the last city. The length of the ith road is wi.\n\nLet dist(u, v) be the length of the shortest path that goes between city u and city v. Your task is to find the total sum of dist(u, v) for all pairs (u, v) (1 ≤ u < v ≤ N).\n\nThe first line of input contains a single integer N (3 ≤ N ≤ 2 × 105), the number of cities.\n\nThe second line of input contains N space-separated integers wi (1 ≤ wi ≤ 1000), the ith value represents the length of the ith road.\n\nPrint the required sum on a single line.\n\n## Input\n\nThe first line of input contains a single integer N (3 ≤ N ≤ 2 × 105), the number of cities.The second line of input contains N space-separated integers wi (1 ≤ wi ≤ 1000), the ith value represents the length of the ith road.\n\n## Output\n\nPrint the required sum on a single line.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ with $ 3 \\leq N \\leq 2 \\times 10^5 $.  \nLet $ w = (w_1, w_2, \\dots, w_N) $ be a sequence of positive integers representing road lengths, where $ w_i $ is the length of the road between city $ i $ and city $ i+1 $ for $ 1 \\leq i < N $, and $ w_N $ is the length of the road between city $ N $ and city $ 1 $.  \nThe graph is a cycle $ C_N $ with edge weights $ w_i $.\n\nLet $ \\text{dist}(u, v) $ denote the shortest path distance between cities $ u $ and $ v $ along the cycle.\n\n**Constraints**  \n$ 1 \\leq w_i \\leq 1000 $ for all $ i \\in \\{1, \\dots, N\\} $\n\n**Objective**  \nCompute the sum:  \n$$\n\\sum_{1 \\leq u < v \\leq N} \\text{dist}(u, v)\n$$  \nwhere $ \\text{dist}(u, v) = \\min\\left( \\sum_{i=u}^{v-1} w_i, \\sum_{i=v}^{u-1} w_i \\right) $ (with indices taken modulo $ N $, and the sum over a circular segment).","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10140D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}