LYK有一个长度为n的序列a。
他最近在研究平均数。
他甚至想知道所有区间的平均数，但是区间数目实在太多了。
为了方便起见，你只要告诉他所有区间(n*(n+1)/2个区间)中第k大的平均数就行了。

输入

第一行两个数n,k(1<=n<=100000,1<=k<=n*(n+1)/2)。
接下来一行n个数表示LYK的区间(1<=ai<=100000)。

输出
一行表示第k大的平均数，误差不超过1e-4就算正确。

输入样例
5 3
1 2 3 4 5

输出样例
4.000

这道题目仔细想一下，不难想到可以二分去做。于是我们考虑二分第k大的平均数。

然后让所有数字都减去我们当前二分的mid，之后，我们就相当于是找有多少个区间的和大于等于0.

这个一眼看去很难找。但是我们取前缀和之后，就能发现实际上是求前缀和的正序对。所以我们直接前缀和之后，树状数组维护。

但是我们还要注意，如果当前的前缀和本身就大于等于0，要答案加一，最后判断区间个数是否大于等于k即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
const double eps=1e-5;
int n,k,m,d[N];
double l=1,r=1e5,a[N],b[N];
inline void add(int x){for(;x<=m;x+=(x&(-x))) d[x]+=1;}
inline int ask(int x){int s=0; for(;x;x-=(x&(-x))) s+=d[x]; return s;}
inline int check(double mid){
	vector<double> v; int res=0; memset(d,0,sizeof d);
	for(int i=1;i<=n;i++)	a[i]-=mid;
	for(int i=1;i<=n;i++)	a[i]+=a[i-1],v.push_back(a[i]);
	sort(v.begin(),v.end());	v.erase(unique(v.begin(),v.end()),v.end());
	m=v.size();
	for(int i=1;i<=n;i++){
		int k=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
		res+=ask(k);	add(k);
		if(a[i]>=0)	res++;
	}
	for(int i=1;i<=n;i++)	a[i]=b[i];
	return res>=k;
}
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)	cin>>a[i],b[i]=a[i];
	while(r-l>eps){
		double mid=(l+r)/2;
		if(check(mid))	l=mid;
		else	r=mid;
	}
	printf("%.5lf\n",l);
	return 0;
}