#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

# 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 2^{20} tribes. The tribes own cities **evenly spaced** along the perimeter of the wasteland, with the cities numbered clockwise from 0 to 2^{20} - 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 RLM^{2}.

# 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 RLM^{2}.

# 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 RLM^{2}. Since there is only one pair of intersecting highways, the program prints 4 / 1 = 4.000 (3 decimal places).

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 5 | 5 | 1s | 128MB | Minimum |

2 | 10 | 5 | 1s | 128MB | Minimum |

3 | 30 | 5 | 1s | 128MB | Minimum |

4 | 55 | 5 | 1s | 4MB | Minimum |

5 | 0 | 1 | 1s | 128MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o highways -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512