Description

某个游戏在游戏者进行完一局之后，会给出这一局的分数。现在游戏制作者需要新增一个功能，使得它在给出分数

的同时，能够给出这局游戏的得分在游戏者之前进行的局的得分中排第几（简单的说，就是计算之前有多少局的分

数比这一局得分高，然后将这个值加一输出）。现在游戏公司找到了你，希望你能解决他们的难题。

Input

第一行一个整数n表示游戏者总共进行过的局数。以下n行每行一个整数，表示该局的得分。

Output

仅一个数，表示你的系统需要输出的n个数的平均值。保留两位小数输出。

Sample Input

5

100

200

150

170

50

Sample Output

2.20

说明：

要输出的五个排名值分别是：1、1、2、2、5，平均值为2.20。

数据范围：

n不超过100000，得分的值为非负整数，并且不超过109。

HINT

思路

splay直接模拟题目要求。

代码

#include 
    
     const int maxn=100000;struct splay_tree{  int fa[maxn+10],son[2][maxn+10],val[maxn+10],size[maxn+10],cnt[maxn+10],root,tot;  inline int t(int x)  {    return son[1][fa[x]]==x;  }  inline int updata(int x)  {    return size[x]=size[son[0][x]]+size[son[1][x]]+cnt[x];  }  inline int rotate(int x)  {    int k=t(x),f=fa[x];    if(fa[f])      {        son[t(f)][fa[f]]=x;      }    fa[x]=fa[f];    if(son[!k][x])      {        fa[son[!k][x]]=f;      }    son[k][f]=son[!k][x];    fa[f]=x;    son[!k][x]=f;    updata(f);    updata(x);    return 0;  }  inline int splay(int x,int c)  {    while(fa[x]!=c)      {        int f=fa[x];        if(fa[f]==c)          {            rotate(x);          }        else if(t(x)==t(f))          {            rotate(f);            rotate(x);          }        else          {            rotate(x);            rotate(x);          }      }    if(!c)      {        root=x;      }    return 0;  }  inline int work(int x)  {    if(!root)      {        ++tot;        root=tot;        fa[tot]=son[0][tot]=son[1][tot]=0;        size[tot]=cnt[tot]=1;        val[tot]=x;        return 1;      }    int now=root;    while(now)      {        if(val[now]==x)          {            ++cnt[now];            splay(now,0);            return size[son[1][now]]+1;          }        else          {            int k=(val[now]