So28_Bai4.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 100005;

int n; ll m;
int a[N], b[N], l[N], r[N];

bool check(int x) {
  for (int i = 1; i <= n; i++) {
    l[i] = r[i] = 0;
  }
  for (int i = 1; i <= n; i++) {
    b[i] = a[i] >= x ? a[i] : x;
  }
  for (int i = 1; i <= n; i++) {
    l[i] = i > 1 ? max(b[i], l[i - 1]) : b[i];
  }
  for (int i = n; i >= 1; i--) {
    r[i] = i < n ? max(b[i], r[i + 1]) : b[i];
  }
  ll sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += max(0, min(l[i - 1], r[i + 1]) - b[i]);
  }
  return sum >= m;
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  int l = 0, r = 2e9, ans = -1;
  while (l <= r) {
    int x = l + (r - l) / 2;
    if (check(x)) {
      ans = x;
      l = x + 1;
    }
    else {
      r = x - 1;
    }
  }
  cout << ans << '\n';
}