n people come to a river in the night. There is a narrow bridge, but it can hold only two people at a time. They have one torch and, because it's night, the torch has to be used when crossing the bridge. The movement across the bridge without a torch is prohibited.
Each person has a different crossing speed; the speed of a group is determined by the speed of the slower member. Your job is to determine a strategy that gets all n people across the bridge in the minimum time.
Consists of multiple test cases. The first line of each test case contains the number of people n (n ≤
103), and the second line gives the sequence of n numbers - the crossing times for each of the people. Nobody takes more than
104 seconds to cross the bridge.
For each test case print the next information. The first line must contain the total number of seconds required for all n people to cross the bridge. The following lines give a strategy for achieving this time. Each line contains either one or two integers, indicating which person or people form the next group to cross. Each person is indicated by the crossing time specified in the input. Although many people may have the same crossing time the ambiguity is of no consequence. Note that the crossings alternate directions, as it is necessary to return the flashlight so that more may cross. If more than one strategy yields the minimal time, any one will do.
4 1 2 5 10 3 1 2 3
17 1 2 1 5 10 2 1 2 6 1 2 1 1 3