During the holidays, Bajtazar became a lover of good literature. He read a great many books that he borrowed from the library. One day, his friend Wyjatek visited him and became interested in one of the borrowed books. After much persuasion, Bajtazar, forgetting his previous problems with Wyjatek, finally agreed to lend it to him.

The holidays passed quickly. The new school year began (although in Bajtocja it starts exceptionally late – 10 Terabytes) and the time came to return the books to the library. Bajtazar remembered that he had lent one of them to Wyjatek. When he asked for its return, Wyjatek admitted that he had lost it while having fun at Lollobrygida during his stay at the resort. This greatly worried poor Bajtazar, as he knew he would have a lot of trouble because of it.

When he told the ladies at the library everything, they decided that he would have to pay a penalty for his reckless behavior and ordered him to come on 0110 (the equivalent of our Saturday) to help them sort library cards. Since several of Bajtazar's friends had already served such a penalty, the cards are in many sorted files of various sizes, and Bajtazar's task is to combine them into one file.

Since Bajtazar had already planned his day and does not want to disappoint the librarians again, you must help him write a program that will allow him to determine how much time sorting the cards will take and to determine the appropriate order of merging the files so that he can do it as quickly as possible.

Bajtazar can only merge two files of cards at a time. For simplicity, we assume that the time to merge two files is equal to the sum of their lengths.

Task

Write a program that:

• reads:
  • the number of library card files that need to be merged into one sorted file,
  • the lengths of the files,
• calculates:
  • the minimum total time to sort the cards in the library,
  • the order of merging the files that results in this time,
• prints the result.

Input

The input consists of exactly two lines. The first line contains the number $n$ ($2 \le n \le 100\,000$) of files to be merged, and the second line contains $n$ numbers $s_1, s_2, \dots, s_n$, separated by single spaces, where $s_i$ denotes the length of the file with number $i$ ($1 \le s_i \le 10\,000$).

Output

Your program should print $n$ lines. The first line should contain exactly one number equal to the minimum time required to merge all files into one. Each of the following lines corresponds to the merging of two files. The line with number $i+1$ ($1 \le i \le n-1$) should contain two integers $k_i, l_i$ separated by a single space, $1 \le k_i < l_i \le n$. These numbers indicate that in the $i$-th step, Bajtazar merges two files with numbers $k_i$ and $l_i$. The newly created file receives the number $k_i$, and its length is equal to the sum of the lengths of files $k_i$ and $l_i$.

If there are multiple optimal sequences for merging the files, your program should print only one of them.

Examples

Input 1

4
1 2 4 7

Output 1

24
1 2
1 3
1 4