提示: 欢迎访问OurACM平台。
Problem 1319 Blocks of Stones

Accept: 186    Submit: 758
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

There are n blocks of stones in a line laying on the ground. Now you are to merge these blocks of stones together with the restriction that you can only merge the neighbouring blocks each time. The score you get for each merging is the number of stones the new blocks has.

Before merging, you are allowed to swap a neighbouring block. You are to calculate the minimal score you will get during the merging process, and the swap position.

Input

There are multiple test cases. For each case, the first line contains a integer n(n<=100), representing the number of blocks. The second line contains n integers, representing number of stones in each blocks

Output

For each case, output 2 lines. The first line contains a single integer, representing the minimal score. The second line contains to integers in the form "(k,k+1)", representing the swap position. If there is more than one swap position which can be the minimal score, output the one with the largest k. You should note that : If swap is not needed output "(0,1)".

Sample Input

3 2 5 1 3 1 2 5

Sample Output

11 (2,3) 11 (0,1)

Source

chenyan

Submit  Back  Status  Discuss