#include<bits/stdc++.h>
using namespace std;
#define int long long
const int TAILLE_MAX=100*1000+5,INFINI=1000*1000*1000;
int nbVal,posInit,tempsInit;
int val[TAILLE_MAX];
void afficher(vector<int> v) {
for (int i:v) {
cout<<i<<" ";
}
cout<<endl;
}
vector<int> calcCumu(vector<int> v) {
vector<int> ans={0};
int somCour=0;
for (int i:v) {
somCour+=i;
ans.push_back(somCour);
}
return ans;
}
bool verif(int temps) {
//cout<<temps<<endl;
vector<int> listeGau,listeDro;
for (int i=posInit;i>1;i--) {
listeGau.push_back(2*temps-val[i]+val[i-1]);
}
for (int i=posInit+1;i<=nbVal;i++) {
listeDro.push_back(2*temps-val[i]+val[i-1]);
}
vector<int> cumuGau=calcCumu(listeGau),cumuDro=calcCumu(listeDro);
//afficher(cumuGau);
//afficher(cumuDro);
int tailleGau=cumuGau.size(),tailleDro=cumuDro.size();
/*for (int i:cumuGau) {
for (int j:cumuDro) {
if (i+j>=0) {
cout<<1<<" ";
}
else {
cout<<0<<" ";
}
}
cout<<endl;
}
cout<<endl;*/
int minCour=INFINI*INFINI,maxCour=-INFINI*INFINI,posMin=0,posMax=0;
vector<pair<int,int>> minJusquaGau,maxJusquaGau,minDepuisGau,maxDepuisGau;
for (int i=0;i<tailleGau;i++) {
if (minCour>cumuGau[i]) {
minCour=cumuGau[i];
posMin=i;
}
if (maxCour<cumuGau[i]) {
maxCour=cumuGau[i];
posMax=i;
}
minJusquaGau.push_back({minCour,posMin});
maxJusquaGau.push_back({maxCour,posMax});
}
minCour=INFINI*INFINI;
maxCour=-INFINI*INFINI;
for (int i=tailleGau-1;i>=0;i--) {
if (minCour>cumuGau[i]) {
minCour=cumuGau[i];
posMin=i;
}
if (maxCour<cumuGau[i]) {
maxCour=cumuGau[i];
posMax=i;
}
minDepuisGau.push_back({minCour,posMin});
maxDepuisGau.push_back({maxCour,posMax});
}
reverse(minDepuisGau.begin(),minDepuisGau.end());
reverse(maxDepuisGau.begin(),maxDepuisGau.end());
minCour=INFINI*INFINI;
maxCour=-INFINI*INFINI;
vector<pair<int,int>> minJusquaDro,maxJusquaDro,minDepuisDro,maxDepuisDro;
for (int i=0;i<tailleDro;i++) {
if (minCour>cumuDro[i]) {
minCour=cumuDro[i];
posMin=i;
}
if (maxCour<cumuDro[i]) {
maxCour=cumuDro[i];
posMax=i;
}
minJusquaDro.push_back({minCour,posMin});
maxJusquaDro.push_back({maxCour,posMax});
}
minCour=INFINI*INFINI;
maxCour=-INFINI*INFINI;
for (int i=tailleDro-1;i>=0;i--) {
if (minCour>cumuDro[i]) {
minCour=cumuDro[i];
posMin=i;
}
if (maxCour<cumuDro[i]) {
maxCour=cumuDro[i];
posMax=i;
}
minDepuisDro.push_back({minCour,posMin});
maxDepuisDro.push_back({maxCour,posMax});
}
reverse(minDepuisDro.begin(),minDepuisDro.end());
reverse(maxDepuisDro.begin(),maxDepuisDro.end());
//cout<<"deb OK"<<endl;
int valMinGau=minJusquaGau.back().first,valMaxGau=maxJusquaGau.back().first,posMaxGau=maxJusquaGau.back().second;
int valMinDro=minJusquaDro.back().first,valMaxDro=maxJusquaDro.back().first,posMaxDro=maxJusquaDro.back().second;
//cout<<"!"<<posMaxGau<<" "<<posMaxDro<<endl;
if (valMinGau+valMaxDro<0 or valMinDro+valMaxGau<0) {
return false;
}
int posGau=posMaxGau-1,posDro=posMaxDro-1;
while (posGau>=0 and posDro>=0) {
if (maxJusquaGau[posGau].first+minJusquaDro[posDro].first>=0) {
posGau=maxJusquaGau[posGau].second-1;
}
else if (maxJusquaDro[posDro].first+minJusquaGau[posGau].first>=0) {
posDro=maxJusquaDro[posDro].second-1;
}
else {
return false;
}
}
//cout<<"mid OK"<<endl;
/*for (auto i:maxDepuisGau) {
cout<<i.first<<" "<<i.second<<"\t";
}
cout<<endl;
for (auto i:maxDepuisDro) {
cout<<i.first<<" "<<i.second<<"\t";
}
cout<<endl;*/
posGau=posMaxGau+1;
posDro=posMaxDro+1;
while (posGau<tailleGau and posDro<tailleDro) {
//cout<<posGau<<" "<<posDro<<endl;
if (maxDepuisGau[posGau].first+minDepuisDro[posDro].first>=0) {
posGau=maxDepuisGau[posGau].second+1;
}
else if (maxDepuisDro[posDro].first+minDepuisGau[posGau].first>=0) {
posDro=maxDepuisDro[posDro].second+1;
}
else {
return false;
}
}
//cout<<"fin OK"<<endl;
return true;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>nbVal>>posInit>>tempsInit;
for (int i=1;i<=nbVal;i++) {
cin>>val[i];
}
verif(23437500);
int deb=0,fin=INFINI,mid;
while (deb!=fin) {
mid=(deb+fin)/2;
if (verif(mid)) {
fin=mid;
}
else {
deb=mid+1;
}
}
cout<<(deb+tempsInit-1)/tempsInit<<endl;
return 0;
}
