#include <bits/stdc++.h>   using namespace std;   long long sum_prefix(vector<long long> &t, int len) {     long long res = 0;     int i = len;     while (i >= 0) {       res += t[i];       i &= (i + 1);       i--;     }     return res;   }   long long sum_interval(vector<long long> &t, int l, int r) {     return sum_prefix(t, r) - sum_prefix(t, l - 1);   }   void plus_value(vector<long long> &t, int num, long long val) {     int N = t.size();     int i = num;     while (i < N) {       t[i] += val;       i |= (i + 1);     }   }   void init(vector<int> &a, vector<long long> &t) {     int i;     int N = a.size();     t.assign(N, 0);     for (i = 0; i < N; i++) plus_value(t, i, a[i]);   }   const int MAXN = 200005;   const int MAXQ = 200005;   vector<int> count_i(MAXN, 0);   vector<int> sum_i(MAXN, 0);   vector<long long> coord;   int s;   struct active {     int type;     long long a1;     long long a2;   };   int get_index(long long a) {     return lower_bound(coord.begin(), coord.end(), a) - coord.begin();   }   int main() {     int i;     set<long long>::iterator J;     int n, q;     cin >> n >> q;     vector<active> a(q);     vector<long long> now_v(n);     set<long long> coord_set;     for (i = 0; i < n; i++) {       cin >> now_v[i];       coord_set.insert(now_v[i]);     }     for (i = 0; i < q; i++) {       cin >> a[i].type;       if (a[i].type == 1) {         cin >> a[i].a1 >> a[i].a2;         a[i].a1--;         coord_set.insert(a[i].a2);       } else         cin >> a[i].a1;     }     for (J = coord_set.begin(); J != coord_set.end(); ++J) coord.push_back(*J);     s = coord.size();     for (i = 0; i < n; i++) {       count_i[get_index(now_v[i])]++;       sum_i[get_index(now_v[i])] += now_v[i];     }     vector<long long> count_i_t, sum_i_t;     init(count_i, count_i_t);     init(sum_i, sum_i_t);     int num;     long long val;     int index_now, index_val;     for (i = 0; i < q; i++) {       if (a[i].type == 1) {         num = a[i].a1;         val = a[i].a2;         index_now = get_index(now_v[num]);         index_val = get_index(val);         plus_value(count_i_t, index_now, -1);         count_i[index_now]--;         plus_value(sum_i_t, index_now, -now_v[num]);         sum_i[index_now] -= now_v[num];         plus_value(count_i_t, index_val, 1);         count_i[index_val]++;         plus_value(sum_i_t, index_val, val);         sum_i[index_val] += val;         now_v[num] = val;       } else {         val = a[i].a1;         int left = 0, right = s - 1;         double ans = -1;         while (right > left) {           int mid = (left + right) / 2;           int now_count = sum_prefix(count_i_t, mid);           if (now_count == 0) {             left = mid + 1;             continue;           }           long long now_sum = sum_prefix(sum_i_t, mid);           long long rest = val - (now_count * coord[mid] - now_sum);           if (rest < now_count * (coord[mid + 1] - coord[mid]))             right = mid;           else             left = mid + 1;         }         int now_count = sum_prefix(count_i_t, left);         long long now_sum = sum_prefix(sum_i_t, left);         long long rest = val - (now_count * coord[left] - now_sum);         ans = coord[left] + rest * 1.0 / now_count;         printf( %.6f n , ans);       }     }   }   