There are N cities in Hacker Country. Each pair of cities are directly connected by a unique directed road, and each road has its own toll that must be paid every time it is used. You're planning a road trip in Hacker Country, and its itinerary must satisfy the following conditions:
You can start in any city.
You must use or more different roads (meaning you will visit or more cities).
At the end of your trip, you should be back in your city of origin.
The average cost (sum of tolls paid per road traveled) should be minimum.
Can you calculate the minimum average cost of a trip in Hacker Country?
Time limits for this challenge are provided here.
The first line is an integer, (number of cities).
The subsequent lines of space-separated integers each describe the respective tolls or traveling from city to city ; in other words, the integer of the line denotes the toll for traveling from city to city .
Note: As there are no roads connecting a city to itself, the integer of line will always be .
Print the minimum cost as a rational number (tolls paid over roads traveled). The greatest common divisor of and should be .
The toll from city to city is . The toll from to is . Your travel cost . Your number of roads traveled is . Thus, we print 3/2 as our answer.