#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 5;
#define int long long
int n, k, a[N];
int c[N], cj[N], cjj[N];

int Get(int i, int j, int p) {
	//当前怪物在i点，能接受最远的攻击为j，
	return (p - i * i) * (c[i] - c[j]) + 2 * i * (cj[i] - cj[j]) - (cjj[i] - cjj[j]);
}

int check(int p) {
	int x = sqrt(p), res = k;
	for (int i = n; i >= 1; i--) {
		int B = Get(i, i + x, p);
		int tmp = (max(-p, a[i] - B) + p) / p;
		res -= tmp;
		if (res < 0)
			return 0;
		c[i - 1] = c[i] + tmp;
		cj[i - 1] = cj[i] + tmp * i;
		cjj[i - 1] = cjj[i] + tmp * i * i;
	}
	return 1;
}

signed main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int l = 1, r = 1e11, res = -1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) {
			r = mid - 1;
			res = mid;
		} else
			l = mid + 1;
	}
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
#define int long long
int n, d[N];
int dis[N][2], son[N][2], f[N], g[N];

//dis[x][0]从x出发到子树的最远距离 dis[x][1]从x出发到子树的次远距离
//son[x][0]从x出发到子树的最远距离经过的儿子，son[x][1]从x出发到子树的次远距离经过的儿子
struct node {
	int v, w;
};

vector<node>e[N];
void dfs1(int x, int fa) {
	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i].v;
		int w = e[x][i].w;
		if (v == fa)
			continue;
		dfs1(v, x);
		if (dis[v][0] + w >= dis[x][0]) {
			dis[x][1] = dis[x][0];
			son[x][1] = son[x][0];
			dis[x][0] = dis[v][0] + w;
			son[x][0] = v;
		} else if (dis[v][0] + w > dis[x][1]) {
			dis[x][1] = dis[v][0] + w;
			son[x][1] = v;
		}
	}
}

void dfs2(int x, int fa, int w) {
	if (son[x][0] != x + n)
		f[x] = dis[x][0];
	else
		f[x] = dis[x][1];

	if (son[fa][0] != x) {
		g[x] = max(g[fa] + w, dis[fa][0] + w);
	} else
		g[x] = max(g[fa] + w, dis[fa][1] + w);
	f[x] = max(f[x], g[x]);
	for (int i = 0; i < e[x].size(); i++) {
		int v = e[x][i].v;
		int w = e[x][i].w;
		if (v == fa)
			continue;
		dfs2(v, x, w);
	}
}

signed main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		e[x].push_back({y, z});
		e[y].push_back({x, z});
	}
	for (int i = 1; i <= n; i++) {
		cin >> d[i];
	}
	for (int i = 1; i <= n; i++) {
		e[i].push_back({i + n, d[i]});
		e[i + n].push_back({i, d[i]});
	}
	dfs1(1, 0);
	dfs2(1, 0, 0);
	for (int i = 1; i <= n; i++) {
		cout << f[i] << '\n';
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, x, a[N];
int tree[N << 2], tag[N << 2];

void pushup(int rt) {
	tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

void pushdown(int l, int r, int rt) {
	if (tag[rt]!=-1) {
		tag[rt << 1] = tag[rt];
		tag[rt << 1 | 1] = tag[rt];
		int mid = (l + r) >> 1;
		tree[rt << 1] = tag[rt] * (mid - l + 1);
		tree[rt << 1 | 1] = tag[rt] * (r - mid);
		tag[rt] = -1;
	}
}

void build(int l, int r, int rt) {
	tag[rt] = -1;
	if (l == r) {
		tree[rt] = (a[l] > x);
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	pushup(rt);
}

void update(int l, int r, int rt, int L, int R, int c) {
	if (L <= l && r <= R) {
		tree[rt] = c * (r - l + 1);
		tag[rt] = c;
		return;
	}
	int mid = (l + r) >> 1;
	pushdown(l, r, rt);
	if (L <= mid)
		update(l, mid, rt << 1, L, R, c);
	if (R > mid)
		update(mid + 1, r, rt << 1 | 1, L, R, c);
	pushup(rt);
}

int query(int l, int r, int rt, int L, int R) {
	if (L <= l && r <= R) {
		return tree[rt];
	}
	pushdown(l, r, rt);
	int mid = (l + r) >> 1;
	int sum = 0;
	if (L <= mid)
		sum += query(l, mid, rt << 1, L, R);
	if (R > mid)
		sum += query(mid + 1, r, rt << 1 | 1, L, R);
	return sum;
}

int main() {
	cin >> n >> m >> x;
	int res = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (a[i] == x) {
			res = i;
		}
	}
	build(1, n, 1);
	for (int i = 1; i <= m; i++) {
		int op, l, r;
		cin >> op >> l >> r;
		if (op == 1) {
			int tmp = query(1, n, 1, l, r); //tmp代表l~r大于x的数的数量
			//r-l+1-tmp
			//l~r 1~5   1 1 1 1 1
			if(tmp!=r-l+1)
				update(1, n, 1, l, r - tmp, 0);
			if(tmp!=0)
				update(1, n, 1, r - tmp + 1, r, 1);
			if (res >= l && res <= r) {
				res = r - tmp;
			}
		} else {
			int tmp = query(1, n, 1, l, r);
			if(tmp!=0)
				update(1, n, 1, l, l + tmp - 1, 1);
			if(tmp!=r-l+1)
				update(1, n, 1, l + tmp, r, 0);
			if (res >= l && res <= r) {
				res = l + tmp;
			}
		}
	}
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 5;
int n, B, m, a[N];
int tree[N << 2], tag[N << 2];
int sum[N];

void pushup(int rt) {
	tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
}

void pushdown(int rt) {
	if (tag[rt]) {
		tag[rt << 1] += tag[rt];
		tag[rt << 1 | 1] += tag[rt];
		tree[rt << 1] += tag[rt];
		tree[rt << 1 | 1] += tag[rt];
		tag[rt] = 0;
	}
}

void build(int l, int r, int rt) {
	if (l == r) {
		tree[rt] = sum[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	pushup(rt);
}

void update(int l, int r, int rt, int L, int R, int c) {
	if (L <= l && r <= R) {
		tag[rt] += c;
		tree[rt] += c;
		return;
	}
	pushdown(rt);
	int mid = (l + r) >> 1;
	if (L <= mid)
		update(l, mid, rt << 1, L, R, c);
	if (R > mid)
		update(mid + 1, r, rt << 1 | 1, L, R, c);
	pushup(rt);
}

double query(int l, int r, int rt, int c) {
	if (l == r) {
		return 1.0 * tree[rt] / l + B;
	}
	pushdown( rt);
	int mid = (l + r) >> 1;
	if (tree[rt << 1] >= c)
		return query(l, mid, rt << 1, c);
	else
		return query(mid + 1, r, rt << 1 | 1, c);
}

signed main() {
	cin >> n >> B >> m;
	int tot = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i] - B;
		tot += a[i];
	}
	build(1, n, 1);
	while (m--) {
		int c, x;
		cin >> c >> x;
		tot -= a[c];
		update(1, n, 1, c, n, x - a[c]);
		tot += x;
		a[c] = x;
		if (tree[1] < 0)
			cout << fixed << setprecision(15) << 1.0 * tot / n << endl;
		else
			cout << fixed << setprecision(15) << query(1, n, 1, 0) << endl;
	}
	return 0;
}