stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include "bits/stdc++.h"

using namespace std;

#define MOD 1000000007

#define Nmax 200010

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)

#define RFOR(i,a,b) for(long long i = (b-1);i>=a;i--)

#define REP(i,n)  FOR(i,0,n)

#define RREP(i,n) RFOR(i,0,n)

#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)

#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)

#define dump(x)  cout << #x << " = " << (x) << endl;

#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

typedef long long ll;

typedef pair<ll,ll> P;

typedef vector<P> Graph;

 

int main() {

	int N;

	cin >> N;

	ll A[Nmax]={};

	ll sumA=0;

	REP(i,N){

		cin >> A[i];

		A[i]-=i+1;

		sumA+=A[i];

	}

	ll S[Nmax]={};

  	sort(A,A+N);

  	S[0]=A[0];

  	REP(i,N-1) S[i+1]+=S[i]+A[i+1];

  	//sort(S,S+N);

	ll b=round((double)(sumA/N)); //仮のb

	ll ans1=0,ans2=0;

	ll mina=0;

	REP(i,N) mina+=abs(A[i]-b);

	FOR(j,1,MOD){

		/*REP(i,N){

      	ans1+=abs(A[i]-b+j);//bを上下に1ずつ広げていく

	  	ans2+=abs(A[i]-b-j);

   		}*/

   		int a=upper_bound(A,A+N,b+j)-A;

   		int c=upper_bound(A,A+N,b-j)-A;

   		ans1=abs(S[a-1]-(b+j)*(a))+abs((S[N-1]-S[a-1])-(b+j)*(N-a));

   		ans2=abs(S[c-1]-(b-j)*(c))+abs((S[N-1]-S[c-1])-(b-j)*(N-c));

   		mina=min(mina,min(ans1,ans2));

   		if(mina!=ans1&&mina!=ans2){//単調増加に転じたらbreak

	   		break;

	   	}

   	}

	cout << mina << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.6305018573404664x):
#include "bits/stdc++.h"

using namespace std;

#define MOD 1000000007

#define Nmax 200010

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)

#define RFOR(i,a,b) for(long long i = (b-1);i>=a;i--)

#define REP(i,n)  FOR(i,0,n)

#define RREP(i,n) RFOR(i,0,n)

#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)

#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)

#define dump(x)  cout << #x << " = " << (x) << endl;

#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

typedef long long ll;

typedef pair<ll,ll> P;

typedef vector<P> Graph;

 

int main() {//答え聞いた後版

	int N;

	cin >> N;

	ll A[Nmax]={};

	REP(i,N){

		cin >> A[i];

		A[i]-=i+1;

	}

  	sort(A,A+N);

	ll b=A[(N-1)/2];//med

	ll mina=0;//ans

	REP(i,N) mina+=abs(A[i]-b);



	cout << mina << endl;

	return 0;

}
// Slower C++ solution:
//#include "bits/stdc++.h"



#include <iostream>

#include <array>

// #include <map>

// #include <string>

// #include <algorithm>

// #include <numeric>

// #include <limits>



using namespace std;



array<int, 100002> box; // use key 100001



int n;

int min_;

int max_;



int solve() {

	cin >> n;

	for (int i = 0; i < n; i++) {

		cin >> min_ >> max_;

		for (int j = min_; j <= max_; j++) {

			box[j]++;

		}

	}

	for (int i = n + 1; i >= 0; i--) {

		//std::cout << "debug " << i << " " << box[i] << std::endl; // debug

		if (i - 1 <= box[i]) {

			return i - 1;

		}

	}

	return 0;

}



int main() {



	cout << solve() << endl;



	//std::cout << "\e[38;5;0m\e[48;5;40m --- end ---  \e[m" << std::endl; // debug

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.3371639653414633x):
//#include "bits/stdc++.h"



#include <iostream>

#include <array>

// #include <map>

// #include <string>

// #include <algorithm>

// #include <numeric>

// #include <limits>



using namespace std;



array<int, 100002> box; // use key 100001



int n;

int np;

int min_;

int max_;



int solve() {

	cin >> n;

	np = n + 1;

	for (int i = 0; i < n; i++) {

		cin >> min_ >> max_;

		if (min_ > np) {

			continue;

		}

		box[min_ - 1]--;

		max_ = min(max_, np);

		box[max_]++;

	}

	box[np + 2] = 0;

	for (int i = np + 1; i >= 0; i--) {

		box[i] += box[i+1];

		//std::cout << "debug " << i << " " << box[i] << std::endl; // debug

		if (i - 1 <= box[i]) {

			return i - 1;

		}

	}

	return 0;

}



int main() {



	cout << solve() << endl;



	//std::cout << "\e[38;5;0m\e[48;5;40m --- end ---  \e[m" << std::endl; // debug

	return 0;

}
// Slower C++ solution:
//#include "bits/stdc++.h"



#include <iostream>

#include <array>

// #include <map>

// #include <string>

// #include <algorithm>

// #include <numeric>

// #include <limits>



using namespace std;



array<int, 100002> box; // use key 100001



int n;

int min_;

int max_;



int solve() {

	cin >> n;

	for (int i = 0; i < n; i++) {

		cin >> min_ >> max_;

		for (int j = min_; j <= max_; j++) {

			box[j]++;

		}

	}

	for (int i = n + 1; i >= 0; i--) {

		//std::cout << "debug " << i << " " << box[i] << std::endl; // debug

		if (i - 1 <= box[i]) {

			return i - 1;

		}

	}

	return 0;

}



int main() {



	cout << solve() << endl;



	//std::cout << "\e[38;5;0m\e[48;5;40m --- end ---  \e[m" << std::endl; // debug

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.3224662857438716x):
//#include "bits/stdc++.h"



#include <iostream>

#include <array>

// #include <map>

// #include <string>

// #include <algorithm>

// #include <numeric>

// #include <limits>



using namespace std;



array<int, 100002> box; // use key 100001



int n;

int np;

int min_;

int max_;



int solve() {

	cin >> n;

	np = n + 1;

	for (int i = 0; i < n; i++) {

		cin >> min_ >> max_;

		if (min_ > np) {

			continue;

		}

		box[min_ - 1]--;

		max_ = min(max_, np);

		box[max_]++;

	}

	box[np + 2] = 0;

	for (int i = np + 1; i >= 0; i--) {

		box[i] += box[i+1];

		//std::cout << "debug " << i << " " << box[i] << std::endl; // debug

		if (i - 1 <= box[i]) {

			return i - 1;

		}

	}

	return 0;

}



int main() {



	std::ios::sync_with_stdio(false);

	std::cin.tie(0);





	cout << solve() << endl;



	//std::cout << "\e[38;5;0m\e[48;5;40m --- end ---  \e[m" << std::endl; // debug

	return 0;

}
// Slower C++ solution:
#include<iostream>

using namespace std;



int N;

int a,b,ans=0;

int P[100010]={};



int main(){

  cin >> N;

  for(int i=0;i<N;i++){

    cin  >> a >> b;

    for(int j=a-1;j<=b-1;j++){

      P[j]+=1;

    }

  }

  for(int i=0;i<=N+1;i++){

    //cout << P[i] << endl;

  }

  for(int i=1;i<=N+1;i++){

    //cout << P[i] << endl;

    //ans = max(ans,P[i]);

    if(P[i]>=i){

      ans = max(ans,i);

    }

    else if(P[i]==i){

      ans = max(ans,P[i]);

    }

    //cout << i <<":" << ans << endl;

  }

  //if(ans!=0) ans-=1;

  cout << ans << endl;

}




// Faster C++ solution for the same problem (measured speedup: 1.3814735508559868x):
#include<bits/stdc++.h>

using namespace std;

#define int long long

int N,answer;

int table[100000+10],ans[100000+10];

signed main(){

  cin >> N;

    for(int i=0;i<N;i++){

      int a,b;

      cin >> a >> b;

      a--,b--;

      table[a]++;

      table[b+1]--;

    }

    for(int i=1;i<=N;i++){

      ans[i]+=ans[i-1]+table[i];

      //cout << ans[i] << endl;

      if(i<=ans[i]) answer=i;

    }

    cout << answer << endl;

  return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define N 100002

using namespace std;

int n,a,b,d[N],ans;



int main(){

  cin>>n;

  for(int i=0;i<n;i++){

    cin>>a>>b;

    for(int j=a;j<=b;j++)d[j]++;

  }

  ans=1;

  for(int i=n+1;i>=2;i--)

    if(d[i]>=i-1)ans=max(ans,i);

  cout<<ans-1<<endl;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.3368160318897686x):
#include<bits/stdc++.h>

#define N 100005

using namespace std;

int n,a,b,d[N],ans;



int main(){

  cin>>n;

  for(int i=0;i<n;i++){

    cin>>a>>b;

    d[a]++;

    d[b+1]--;

  }

  for(int i=1;i<=n+1;i++)d[i]+=d[i-1];

  ans=1;

  for(int i=n+1;i>=2;i--)

    if(d[i]>=i-1)ans=max(ans,i);

  cout<<ans-1<<endl;

  return 0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <map>

#include <algorithm>

 

#define rep(i,n) for (int i = 0; i < (n); ++i)

  

int n, a, b, friends[100005], fri, maxi;



int main() {

  std::cin.tie(0);

  std::ios::sync_with_stdio(false);



  std::cin >> n;

  rep(i,n) {

    std::cin >> a >> b;

    a--; b--;

    for (int i = a; i <= b; ++i) friends[i]++;

  }

  rep(i,n+1) {

    if (friends[i] >= i) {

        maxi = i;

    }

  }



  std::cout << maxi << std::endl;



  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.3770206054757599x):
#include <iostream>

#include <vector>

#include <map>

#include <algorithm>



#define rep(i,n) for (int i = 0; i < (n); ++i)



int n, a, b, friends[100005], fri, ans;



/***************************************



           imos???version



***************************************/



int main() {

  std::cin.tie(0);

  std::ios::sync_with_stdio(false);



  std::cin >> n;

  rep(i,n) {

    std::cin >> a >> b;

    a--;

    friends[a]++;

    friends[b]--;

  }



  for (int i = 1; i <= n; ++i) friends[i] += friends[i-1];



  rep(i,n+1) {

      if (friends[i] >= i) {

          ans = std::max(ans, i);

      }

  }



  std::cout << ans << std::endl;



  return 0;

}
// Slower C++ solution:
// テ・ツ淞コテヲツ慊ャテ」ツδ?」ツδウテ」ツδ療」ツδャテ」ツδシテ」ツδ?



#include <iostream>

#include <iomanip>

#include <cstdio>

#include <string>

#include <cstring>

#include <deque>

#include <list>

#include <queue>

#include <stack>

#include <vector>

#include <utility>

#include <algorithm>

#include <map>

#include <set>

#include <complex>

#include <cmath>

#include <limits>

#include <cfloat>

#include <climits>

#include <ctime>

#include <cassert>

#include <numeric>

#include <functional>

using namespace std;



#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)

#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)

#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)

#define int long long int



template<typename T> void chmax(T &a, T b) {a = max(a, b);}

template<typename T> void chmin(T &a, T b) {a = min(a, b);}

template<typename T> void chadd(T &a, T b) {a = a + b;}



typedef pair<int, int> pii;

typedef long long ll;



int dx[] = {0, 0, 1, -1};

int dy[] = {1, -1, 0, 0};

constexpr ll INF = 1001001001001001LL;

constexpr ll MOD = 1000000007LL;



int N;

int imos[100010];



signed main() {

    cin >> N;

    rep(i,0,N) {

        int a, b; cin >> a >> b;

        imos[a]++; imos[b+1]--;

    }



    rep(i,1,100010) imos[i] += imos[i-1];

    int ans = 0;

    rep(i,0,100010) {

        // if(i < 10) printf("i = %lld, imos = %lld\n", i, imos[i]);

        if(imos[i] + 1 >= i) chmax(ans, i-1);

    }

    cout << ans << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.1906897893456696x):
// #define _GLIBCXX_DEBUG // for STL debug (optional)

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <string>

#include <cstring>

#include <deque>

#include <list>

#include <queue>

#include <stack>

#include <vector>

#include <utility>

#include <algorithm>

#include <map>

#include <set>

#include <complex>

#include <cmath>

#include <limits>

#include <cfloat>

#include <climits>

#include <ctime>

#include <cassert>

#include <numeric>

#include <fstream>

#include <functional>

#include <bitset>

using namespace std;

using ll = long long int;

using int64 = long long int;

 

template<typename T> void chmax(T &a, T b) {a = max(a, b);}

template<typename T> void chmin(T &a, T b) {a = min(a, b);}

template<typename T> void chadd(T &a, T b) {a = a + b;}

 

int dx[] = {0, 0, 1, -1};

int dy[] = {1, -1, 0, 0};

const int INF = 1LL << 29;

const ll LONGINF = 1LL << 60;

const ll MOD = 1000000007LL;

 

int main() {

    int N; scanf("%d", &N);

    const int MAXN = 100010;

    vector<int> seg(MAXN+5);

    seg[0] = 1;

    for(int i=0; i<N; i++) {

        int a, b;

        scanf("%d%d", &a, &b);

        seg[a]++, seg[b+1]--;

    }



    for(int i=1; i<=MAXN+3; i++) seg[i] += seg[i-1];



    int ans = -1;

    for(int i=1; i<=MAXN; i++) {

        if(seg[i] >= i) {

            chmax(ans, i-1);

        }

    }

    printf("%d\n", ans);

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <sstream>

#include <fstream>

#include <string>

#include <vector>

#include <deque>

#include <queue>

#include <stack>

#include <set>

#include <map>

#include <algorithm>

#include <functional>

#include <utility>

#include <bitset>

#include <cmath>

#include <cstdlib>

#include <ctime>

#include <cstdio> 

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)

#define rangeRep(i, n, m) for(int (i) = (n); (i) < (m); (i)++)



int canGo[100001] = {0};



class Solve {

public:

	Solve() {};

	~Solve() {};



	void solver() {

		int ans = 0;

		int n;

		std::cin >> n;

		std::vector<std::pair<int, int>> friends(n, std::make_pair(0, 0));

		rep(i, n) {

			std::cin >> friends[i].first >> friends[i].second;

			//Exclude myself

			friends[i].first--; friends[i].second--;

		}

		//Record the number of people who can go.

		for (auto& x : friends) {

			rangeRep(i, x.first, x.second+1) {

				canGo[i]++;

			}

		}

		int max = 0;

		rep(i, n+1) {

			if (canGo[i] >= i) {

				max = i;

			}

		}

		std::cout << max << std::endl;

	}

private:



};



int main() {

	Solve solve;

	solve.solver();

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.3776127371103646x):
#include <iostream>

#include <sstream>

#include <fstream>

#include <string>

#include <vector>

#include <deque>

#include <queue>

#include <stack>

#include <set>

#include <map>

#include <algorithm>

#include <functional>

#include <utility>

#include <bitset>

#include <cmath>

#include <cstdlib>

#include <ctime>

#include <cstdio> 

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)

#define rangeRep(i, n, m) for(int (i) = (n); (i) < (m); (i)++)



int canGo[100001] = {0};



class Solve {

public:

	Solve() {};

	~Solve() {};



	void solver() {

		int ans = 0;

		int n;

		std::cin >> n;

		std::vector<std::pair<int, int>> friends(n, std::make_pair(0, 0));

		rep(i, n) {

			std::cin >> friends[i].first >> friends[i].second;

			//Exclude myself

			friends[i].first--; friends[i].second--;

		}

		//Record the number of people who can go.

		for (auto& x : friends) {

			canGo[x.first]++;

			canGo[x.second + 1]--;

		}

		//fill

		rangeRep(i, 1, n + 1) {

			canGo[i] += canGo[i - 1];

		}

		int max = 0;

		rep(i, n+1) {

			if (canGo[i] >= i) {

				max = i;

			}

		}

		std::cout << max << std::endl;

	}

private:



};



int main() {

	Solve solve;

	solve.solver();

	return 0;

}
// Slower C++ solution:
#include<cstdio>



using namespace std;



const int MAX = 100005;

int dp[MAX];



int main(){



  int n;

  scanf("%d",&n);



  while(n--){

    int a,b;

    scanf("%d %d",&a,&b);

    for(int i = a; i <= b; i++) dp[i]++;

  }



  for(int i = MAX-1; i>0; i--)

    if(dp[i] >= i-1){

      printf("%d\n",i-1);

      break;

    }

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.1186421990298627x):
#include<cstdio>



using namespace std;



const int MAX = 100005;

int res[MAX];



int main(){



  int n;

  scanf("%d",&n);



  while(n--){

    int a,b;

    scanf("%d %d",&a,&b);

    res[a-1]++;

    res[b]--;

  }



  int now = 0;

  int ans = 0;

  for(int i = 0; i < MAX; i++){

    now += res[i];

    if(now >= i) ans = i;

  }



  printf("%d\n",ans);

  return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;



int imos[111111];

int main(){

    int n;

    while(cin >> n){

        //memset(imos,0,sizeof(imos));

        for(int i=0;i<n;i++){

            int a,b;

            cin>>a>>b;

            imos[a-1]++;

            imos[b]--;

        }

        for(int i=1;i<111111;i++){

            imos[i]+=imos[i-1];

        }

        int ans=0;

        for(int i=0;i<111111;i++){

            if(imos[i]>=i)ans=max(ans,i);

        }

        cout << ans << endl;

    }

}

// Faster C++ solution for the same problem (measured speedup: 1.132984886121716x):
#include <bits/stdc++.h>

#define rep(i,n) for(int i = 0; i < (int)(n); ++i)

using namespace std; 

const int INF = 1e9;



int main(){

    int n;

    while(cin >> n){

        int diff[100010] = {};

        rep(i,n){

            int a,b;

            cin >> a >> b;

            ++diff[a-1];

            --diff[b];

        }

        int x = 0;

        int ans = 0;

        rep(i,100010){

            x += diff[i];

            if(x >= i) ans = i;

        }

        cout << ans << endl;

    }

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for (int i = a; i < b; i++)

#define REP(i,b) FOR(i,0,b)

#define RFOR(i,a,b) for (int i = a-1; i >= b; i--)

#define RREP(i,a) RFOR(i,a,0)

#define REPALL(i,v) for (int i = 0; i < v.size(); i++)

#define RREPALL(i,v) for (int i = v.size()-1; i >= 0; i--)

#define SORT(v) sort(v.begin(), v.end())

#define MIN_ELEMENT(v) min_element(v.begin(), v.end())

#define MAX_ELEMENT(v) max_element(v.begin(), v.end())

#define COUNT(v,n) count(v.begin(), v.end(), n);

void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}

void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}

void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}

typedef long long ll;

typedef unsigned long long ull;

const int INF = 1e7;

const ll MOD = 1e9 + 7;



vector<int> a,b, sum(111111);

int ans = 1;



int main()

{

    int n;

    cin>>n;

    a.resize(n); b.resize(n);

    REP(i,n) {

        cin>>a[i]>>b[i];

        sum[a[i]]++;

        sum[b[i]+1]--;

    }

    sum[0]++;

    REP(i,100111) {

        sum[i+1] = sum[i] + sum[i+1];

        if (sum[i+1] >= i+1) {

            ans = i+1;

        }

    }

    cout<<ans - 1<<endl;



    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 1.1367653664359274x):
#include <bits/stdc++.h>



#define CEIL(a,b) ((a) / (b) + ((a) % (b) == 0 ? 0 : 1))



using namespace std;

using ll = long long;

using pii = pair<int, int>;



constexpr int MOD = 1'000'000'007;

constexpr int INF = 1'000'000'001;

constexpr ll LLINF = 4'000'000'000'000'000'001;

// constexpr int INF = 2147483647; // 2 * 1e9

// constexpr ll LLINF = 9223372036854775807; // 9 * 1e18



const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1, 0};

const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1, 0};



int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cout << fixed << setprecision(10);

    int n;

    cin >> n;

    vector<int> t(100002);

    for(int i = 0; i < n; ++i){

        int a, b;

        cin >> a >> b;

        --a; --b;

        t[a] += 1;

        t[b+1] -= 1;

    }

    for(int i = 0; i <= n+1; ++i){

        t[i+1] += t[i];

    }

    for(int i = n + 1; i >= 0; --i){

        if(t[i] >= i){

            cout << i << "\n";

            return 0;

        }

    }

    cout << "0\n";

    return 0;

}
// Slower C++ solution:
#include <iostream>

using namespace std;



int main(){

  int n;



  while(cin>>n){

    int dec[100002];

    int inc[100002];



    for(int i=0;i<100002;i++){

      dec[i] = 0;

      inc[i] = 0;

    }



    for(int i=0;i<n;i++){

      int a,b;

      cin>>a>>b;

      inc[a]++;

      dec[b]++;

    }



    int now = 0;

    int ans = 0;



    for(int i=0;i<100002;i++){

      now += inc[i];

      if(now + 1 >= i) ans = max(ans, i);

      now -= dec[i];

    }



    cout<<ans-1<<endl;

  }

}

// Faster C++ solution for the same problem (measured speedup: 1.0998926792774764x):


#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;



int n;

int pls[100002], mns[100002];



int main(){

  while(scanf("%d", &n) != EOF){

    memset(pls, 0, sizeof(pls));

    memset(mns, 0, sizeof(mns));



    for(int i = 0; i < n; i++){

      int a, b;

      scanf("%d%d", &a, &b);

      pls[a]++;

      mns[b]++;

    }



    int sum = 0;

    int ans = 1;



    for(int i = 1; i <= n + 1; i++){

      sum += pls[i];



      if(i <= sum + 1){

        ans = i;

      }



      sum -= mns[i];

    }



    cout << ans - 1 << endl;

  }

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <vector>



using namespace std;



int main() {

	int n;

	cin >> n;

	vector<int> a(n);

	vector<int> b(n);

	vector<int> c(100005, 0);

	int maxi = 0;

	for (int i = 0; i < n; ++i) {

		cin >> a[i] >> b[i];

		maxi = max(maxi, b[i]);

		for (int j = a[i]; j <= b[i]; ++j) c[j]++;

	}



	int ans = 0;

	for (int i = maxi; i > 0; --i) {

		if (i - 1 <= c[i]) {

			ans = i - 1;

			break;

		}

	}

	cout << ans << endl;



	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.1669819983428098x):
#include <iostream>

#include <algorithm>

#include <vector>



using namespace std;



int main() {

	int n;

	cin >> n;

	int a, b;

	vector<int> c(100005, 0);

	int maxi = 0;

	for (int i = 0; i < n; ++i) {

		cin >> a >> b;

		c[a]++;

		c[b + 1]--;

		maxi = max(maxi, b);

	}

	int ans = 0;

	for (int i = 1; i <= maxi; ++i) {

		c[i] += c[i - 1];

		if (c[i] >= i - 1) ans = i - 1;

	}

	cout << ans << endl;



	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int main(){

	int n,h[111111]={};

	cin>>n;

	int a,b;

	for(int i=0;i<n;i++){

		cin>>a>>b;

		h[a]++;

		h[b+1]--;

	}

	int ma=0;

	for(int i=1;i<=n+1;i++){

		h[i]+=h[i-1];

		if(i<=h[i]+1)ma=max(ma,i-1);

	}

	cout<<ma<<endl;

	return 0;

}




// Faster C++ solution for the same problem (measured speedup: 1.441147913902522x):
#include<bits/stdc++.h>

using namespace std;

int im[100010]={};

int main(){

  int n;

  cin>>n;

  for(int i=0;i<n;i++){

    int a,b;

    cin>>a>>b;

    im[a]++;

    im[b+1]--;

  }

  int ans;

  for(int i=1;i<=n+2;i++){

    im[i]+=im[i-1];

    if(im[i-1]>=i-2)ans=i-2;

  }

  cout<<ans<<endl;

  return 0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <queue>

#include <map>

#include <set>

#include <list>

#include <deque>

#include <string>

#include <algorithm>

#include <cmath>

#include <ctype.h>

using namespace std;

#define dump(a) cout << (a) << '\n';

typedef long long Int;

Int mod = 1e9+7;

Int MOD = 998244353;



int main() {

    ios::sync_with_stdio(false);

    Int n, m, d;

    cin >> n >> m >> d;

    double res = 0.0;

    for (Int i = 0; i < m - 1; i++) {

        res += (double)(n - d) * 2.0 / (double)(n * n);

    }

    if (d == 0) res /= 2.0;

    printf("%.12lf\n", res);

    return 0;  

}    

// Faster C++ solution for the same problem (measured speedup: 1.1896587861928347x):
#include <bits/stdc++.h>

using namespace std;



#define dump(x) cout << (x) << '\n'

#define Int int64_t

#define fi first

#define se second

#define all(x) (x).begin(), (x).end()



Int INF = 1e18;

int inf = 1e9;

Int mod = 1e9+7;



int main() {

    double n, m, d;

    cin >> n >> m >> d;

    double x = (n - d) * 2.0;

    if (d == 0) x = n;

    double a = (m - 1.0) / n;

    double b = x / n;

    printf("%.12lf\n", a * b);



    return 0;

}