Description

There are $n$ people lining up at a faucet. Suppose the time each person needs to fill water is $T_i$. Please write a program to find an ordering of these $n$ people that minimizes the average waiting time of all $n$ people.

A person's waiting time does not include their own filling time.

If two people have the same filling time, the one with the smaller index should be placed earlier.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers. The $i$-th integer $T_i$ denotes the $i$-th person's filling time $T_i$.

Output Format

Output two lines. The first line is an ordering that yields the minimum average waiting time. The second line is the average waiting time under this ordering (rounded to two decimal places).

10 
56 12 1 99 1000 234 33 55 99 812

3 2 7 8 1 4 9 6 10 5
291.90

Hint

Constraints: $1 \le n \leq 1000$, $1 \le t_i \leq 10^6$. The $t_i$ are not guaranteed to be distinct.

Translated by ChatGPT 5