接水安排

题目描述

有 n 名同学依次使用一台饮水机。第 i 名同学接水需要 t_i 秒。

在一名同学接水时，排在他后面的同学都需要等待。你可以任意安排同学的接水顺序，希望所有同学等待时间之和最小。

若两名同学接水时间相同，编号小的同学排在前面。学生编号按照输入顺序依次为 1~n。

请输出最优排队顺序，以及在该顺序下所有同学的平均等待时间。

第一名同学的等待时间为 0。

输入格式

第一行输入一个整数 n。

第二行输入 n 个整数 t_1,t_2,...,t_n。

输出格式

第一行输出 n 个整数，表示最优排队顺序中的学生编号。

第二行输出平均等待时间，保留两位小数。

样例输入

4
8 1 5 2

样例输出

2 4 3 1
3.00

样例说明

排队顺序为 2,4,3,1，对应接水时间为 1,2,5,8。

四人的等待时间分别为 0,1,3,8，平均等待时间为 (0+1+3+8)/4=3.00。

数据范围

对于全部数据：

• 1 <= n <= 100000；
• 1 <= t_i <= 10^9。