a292. TOI 2024/03 潛力組：雕像排序成本

題目描述

N 座雕像依序排成一列，第 i 座的重量為 Wi。每次可以選擇一對相鄰且左邊比右邊重的雕像，交換兩者的位置；這次交換耗費的電力等於兩座雕像的重量和。

持續進行這種交換，直到重量由小到大排列。請計算完成排序所需的總電力。

輸入格式

第一行為 N，第二行為 N 個重量。

• 3 ≤ N ≤ 200000
• 1 ≤ Wi ≤ 1000000

輸出格式

輸出總耗電量，為一個非負整數。

來源

TOI 2024 年 3 月潛力組〈雕像排序成本〉。以自寫文字重述，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202403/Sculpture.pdf