HIST2  Histogram
In statistics, a histogram is a graphical display of tabulated frequencies, shown as bars. It shows what proportion of cases fall into each of several categories. It is a polygon composed of a sequence of rectangles aligned at a common base line. In this problem all rectangles have a width of unit length. But their heights are distinct. Some permutation of the heights will give the maximum perimeter. Your task is to find the maximum perimeter of the histogram and the number of permutations that give the maximum perimeter.
In the image Figure (a) shows a histogram with heights {1,2,3,4} (1st sample testcase) and has a perimeter of 16 units. Figure (b) shows one of the permutations {3,1,2,4} having the maximum perimeter of 20 units.
Input
Input consists of multiple test cases. Each test case describes a histogram and starts with an integer N, 2 ≤ N ≤ 15, denoting the number of rectangles it is composed of. Next line consists of N space separated positive integers representing the heights of the rectangles. All heights are distinct and less than or equal to 100. N=0 indicates the end of tests. There are atmost 50 test cases.
Output
For each test case output the maximum possible perimeter of the histogram and the number of permutations that give maximum perimeter in a single line, separated by a single space.
Example
Input: 4 1 2 3 4 3 2 6 5 0 Output: 20 8 24 2
hide comments
aspro:
20160606 14:55:36
very nice question ...loved solving this...also solve ASSIGN in spoj 

erdenebayr_d:
20160514 10:25:34
@naruto09: number of permutations equal maximum perimeter 

naruto09:
20151207 14:33:58
can someone help me understand how 8 came in test case 1..?? 

xxbloodysantaxx:
20150715 19:04:52
WoW!! 

Sudharsansai:
20150324 15:30:37
DP+Bitmasking for beginners.. 

yaswanth:
20140817 14:49:21
great problem!! 

alphaplus:
20140303 23:44:14
very nice question


Smithers:
20140303 23:44:14
@madhav Short answer: yes. The long answer would probably be a spoiler, but I can say that my solution turned out to be surprisingly straightforward, at least in code  arriving at it and convincing myself that it worked was more complicated. My background is maths not computer science and getting to my solution is a little involved; most programmers may well be more at home with your solution. Last edit: 20101026 22:37:01 
Added by:  Swarnaprakash 
Date:  20081129 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 
Resource:  Kurukshetra 09 OPC 