Problem Statement
Time limit: 1s, Memory limit: 128MB
In Parrebia, there is a circular wasteland measuring 2 Really Long Miles (RLM) in diameter, which, 1000 years after the Really Devastating Event, has been colonised by 220 tribes. The tribes own cities evenly spaced along the perimeter of the wasteland, with the cities numbered clockwise from 0 to 220 - 1 starting from the Northernmost city. N (N ≥ 4) of these cities are under the control of the massive conglomerate Parrebian Toller (PTOL), which has built straight highways between every pair of cities it controls and has lined every highway evenly and densely with toll booths.
Toller has decided to embark on its millenium project, Toller ME, where every toll booth along every highway is upgraded to provide WiFi service. For every pair of booths on any two distinct, intersecting highways, however, there is a possibility that their WiFi signals may interfere. Note that two highways do not intersect if they share the same endpoint. To correct for this, Toller must conduct expensive tests on every such pair of booths. It is not difficult to see that the cost to conduct experiments for every pair of possibly interfering booths along any two intersecting highways is proportional to the product of their lengths.
To aid Toller in its calculations, find the average product of lengths of a pair of intersecting highways in units of RLM2.
Subtasks
- Subtask 1 (5%): N ≤ 50
- Subtask 2 (10%): N ≤ 100
- Subtask 3 (30%): N ≤ 1000
- Subtask 4 (55%): N ≤ 200000
- Subtask 5 (0%): Sample Input
Input
The input consists of N + 1 lines. The first line contains N, the number of cities under Toller's control. The next N lines contain the numerical identifiers of each city, one per line.
Output
Your program should output a single line containing a single number rounded to 3 decimal places, which is the average product of lengths of a pair of intersecting highways in units of RLM2.
Sample Input
4
0
262144
524288
786432
Sample Output
4.000
Sample Output Explanation
Only the highways (0, 524288) and (262144, 786432) intersect, and since each of them is a diameter of the wasteland, their lengths are 2 RLM each. The product of their lengths is 2 RLM × 2 RLM = 4 RLM2. Since there is only one pair of intersecting highways, the program prints 4 / 1 = 4.000 (3 decimal places).