You local post office spends a lot of time sorting the mail so that as the postie drives or rides down the street, everything is in order. They are wondering how effective this sorting is, and how it would compare if they simply left the postie to deliver mail in whatever order he or she pulled it out of the mailbag.
You are to write a program which computes the best and worst case scenarios for a postie delivering mail down one street. To accomodate all factors involved in the time taken to deliver mail, the post office has modelled the time taken to get from one mail box to another as being close to the square of the difference of the house numbers. This means that two letters delivered to the same place one after the other are delivered at the same time.
Your program must read in the details for a street worth of mail and print out the best possible (shortest time) and worst possible (longest time) taken to deliver all the mail. You may choose in each case where the postie starts and ends delivering. The output times are given in integer time units. Multiple letters can be delivered to the same house at the same time, or they can be delivered seperately.
Each line of input contains the number of letters, followed by the house number of each letter, seperated by spaces. The letters appear in any order, and the house numbers can range from 1 to 500. The number of letters will be a multiple of two between 2 and 100 inclusive.
Your output for each line of input is to be a single line with the minimum and maximum times seperated by a single space. The input file will be terminated by a mail set with 0 (zero) letters to be delivered.
2 5 10 4 10 7 4 8 4 1 1 500 500 0
25 25 14 61 249001 747003