友爱的 YY 小朋友,正在学习快速排序，聪明的他很快就发现，快排是会出现退化的情况的。
于是乎他友爱地发明了用随机化的方法。
但是这个时候友爱的小 YY 还是不满足于现状，他想知道怎么证明快速排序的期望复杂度是 。
于是他决定自己定义代价自己算，他的快速排序过程是这样的：
首先在待排序的数字里随机选取一个 作为基准点,然后代价变量 划分代价（划分代价即在 的左边比 大的数字的个数 + 在 的右边比 小的数字的个数）+ 将两部分分别递归下去的 。
注意：划分的过程中保持相对位置不变。
聪明又友爱的他很快就发现 的最大期望是 的级别的，但是好学的他还想知道对于一个具体的，数字不重复的序列， 的期望是多少。当然你要知道 YY 是要拿 UOI 金牌的人，所以他决定让你来完成计算的工作。
