#include <array>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <vector>

using namespace std;

int main() {
  int n, maxd, maxcap;
  cin >> n >> maxd >> maxcap;
  vector<int> v(n);
  auto valid = [&](int lhs, int rhs) -> bool {
    map<int, int> dp;
    int amt = 0;
    auto upd = [&](int k, int v) -> void {
      dp[k] += v;
      amt += v;
      assert(dp[k] >= 0);
      if(dp[k] == 0) dp.erase(k);
    };
    auto trytake = [&](int k, int v, bool allowinit) -> int {
      auto it = dp.upper_bound(k);
      if(it == dp.begin()) return 0;
      it--;
      if(it->first == -1 && !allowinit) return 0;
      int use = min(it->second, v);
      assert(use > 0);
      upd(it->first, -use);
      return use;
    };
    upd(-1, maxcap);
    deque<array<int, 2>> demands;
    for(int i = 0; i < n; i++) {
      upd(i, v[i]);
      {
        int inner = lhs;
        while(inner > 0) {
          int go = trytake(i, inner, true);
          if(go == 0) return false;
          inner -= go;
        }
      }
      if(rhs > lhs) demands.push_back({i, rhs - lhs});
      while(amt > maxcap) {
        if(demands.size() == 0) {
          if(!dp.count(-1)) return false;
          int take = min(amt - maxcap, dp[-1]);
          upd(-1, -take);
          if(amt > maxcap) return false;
          break;
        }
        int go = trytake(demands[0][0], min(amt - maxcap, demands[0][1]), false);
        if(go == 0) demands.pop_front();
        else {
          demands[0][1] -= go;
          if(demands[0][1] == 0) demands.pop_front();
        }
      }
    }
    return true;
  };
  for(auto& x: v) cin >> x;
  int lhs = 0;
  int rhs = maxd;
  int rans = -1;
  while(lhs <= rhs) {
    int mid = (lhs+rhs)/2;
    if(valid(0, mid)) {
      rans = mid;
      rhs = mid-1;
    }
    else lhs = mid+1;
  }
  lhs = 0;
  rhs = maxd;
  int lans = -1;
  while(lhs <= rhs) {
    int mid = (lhs+rhs)/2;
    if(valid(mid, maxd)) {
      lans = mid;
      lhs = mid+1;
    }
    else rhs = mid-1;
  }
  cout << max(0, (rans-lans)) << "\n";
}