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

using namespace std;



#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>

void __f(const char* name, Arg1&& arg1) {

  cerr << name << " : " << arg1 << "\n";

}

template <typename Arg1, typename... Args>

void __f(const char* na, Arg1&& arg1, Args&&... args) {

  const char* c = strchr(na + 1, ',');

  cerr.write(na, c - na) << " : " << arg1 << " , ";

  __f(c + 1, args...);

}

#define endl "\n"

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

#define UNIQUE(v) sort(all(v)),v.erase(unique(all(v)),v.end())

typedef long long LL;

typedef pair <int,int> pii;

const double pi = acos(-1.0);

const double eps = 1e-8;

const int mod = 1e9 + 7;

const int inf = 1e9;

const LL INF = 1e16;

const int N = 2e5 + 5;



map <LL,LL> dp[ N ];

int n;

LL a[ N ];



LL solve(int idx, int taken) {

  int need = n/2 - (n - idx + 1)/2;

  if (taken < need) return -INF;

  if (idx >= n) return taken == n/2 ? 0 : -INF;

  if (dp[idx].count(taken)) return dp[idx][taken];

  LL ret = -INF;

  ret = max(ret, solve(idx + 2, taken + 1) + a[idx]);

  ret = max(ret, solve(idx + 1, taken));

  return dp[idx][taken] = ret;

}

int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(0); cout.tie(0);

  #ifdef LOCAL

    freopen("input.txt", "r", stdin);

  #endif // LOCAL

  cin >> n;

  for (int i = 0; i < n; i++) cin >> a[i];

  cout << solve(0, 0) << endl;

  return 0;

}


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

#include <stdio.h>

#include <string>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <vector>

#include <set> 

#include <map>

#include <queue>

#include <deque>

#include <stack>

#include <bitset>

#include <iomanip>

using namespace std;

#define assem99 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define ll long long

#define ull unsigned long long

#define ld long double

#define ii pair<int, int>

#define pll pair<ll, ll>

#define vii vector<ii>

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

#define F first

#define S second

#define sz(a) (int)(a).size()

#define ReadFile freopen("input.txt","r",stdin)

#define WriteFile freopen("output.txt","w",stdout)

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

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

const int MOD = 1e9 + 7, N = 2e5 + 5;

const double pi = acos(-1);



ll n, arr[N], dp[N][3];



ll solve(int id, int taken, int skipped)

{

	if (id >= n) return (taken == n / 2) ? 0 : -1e18;

	if (dp[id][skipped] != -1) return dp[id][skipped];

	ll ans = -1e18;

	if (skipped < 2) ans = max(ans, solve(id + 1, taken, skipped + 1));

	ans = max(ans, solve(id + 2, taken + 1, skipped) + arr[id]);

	return dp[id][skipped] = ans;

}



int main()

{ 

	assem99;

	memset(dp, -1, sizeof(dp));

	cin >> n;

	rep(i, 0, n) cin >> arr[i];

	cout << solve(0, 0, 0);



	return 0;

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

using namespace std;



#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>

void __f(const char* name, Arg1&& arg1) {

  cerr << name << " : " << arg1 << "\n";

}

template <typename Arg1, typename... Args>

void __f(const char* na, Arg1&& arg1, Args&&... args) {

  const char* c = strchr(na + 1, ',');

  cerr.write(na, c - na) << " : " << arg1 << " , ";

  __f(c + 1, args...);

}

#define endl "\n"

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

#define UNIQUE(v) sort(all(v)),v.erase(unique(all(v)),v.end())

typedef long long LL;

typedef pair <int,int> pii;

const double pi = acos(-1.0);

const double eps = 1e-8;

const int mod = 1e9 + 7;

const int inf = 1e9;

const LL INF = 1e16;

const int N = 2e5 + 5;



map <LL,LL> dp[ N ];

int n;

LL a[ N ];



LL solve(int idx, int taken) {

  int need = n/2 - (n - idx + 1)/2;

  if (taken < need) return -INF;

  if (idx >= n) return taken == n/2 ? 0 : -INF;

  if (dp[idx].count(taken)) return dp[idx][taken];

  LL ret = -INF;

  ret = max(ret, solve(idx + 2, taken + 1) + a[idx]);

  ret = max(ret, solve(idx + 1, taken));

  return dp[idx][taken] = ret;

}

int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(0); cout.tie(0);

  #ifdef LOCAL

    freopen("input.txt", "r", stdin);

  #endif // LOCAL

  cin >> n;

  for (int i = 0; i < n; i++) cin >> a[i];

  cout << solve(0, 0) << endl;

  return 0;

}


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

using namespace std;

#define elif else if

typedef long long ll;

typedef unsigned long long ull;

#define DEBUG(x) cout << (x) << endl

#define TGET(a, b) get<b>(a)



#define MAXN 200100



ll arr[MAXN] = {0};

ll odd_pos[MAXN] = {0};

ll even_pos[MAXN] = {0};



ll dp[MAXN] = {0};



int main()

{

    int n;

    scanf("%d", &n);

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

    {

        scanf("%lld", arr + i);

    }



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

    {

        if (i == 1)

        {

            odd_pos[i] = arr[i];

            even_pos[i + 1] = arr[i + 1];

        }

        else

        {

            odd_pos[i] = arr[i] + odd_pos[i - 2];

            even_pos[i + 1] = arr[i + 1] + even_pos[i - 1];

        }

    }

    // ll ans = even_pos[n-1];

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

    // {

    //     ans = max(ans, odd_pos[n] - arr[i]);

    //     ans = max(ans, (odd_pos[i] - arr[i]) + (even_pos[n - 1] - even_pos[i - 1]));

    //     ans = max(ans, (odd_pos[i] - arr[i]) + arr[i + 1] + (odd_pos[n] - odd_pos[i + 2]));

    // }

    // printf("%ld\n", ans);

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

    {

        if (i % 2)

        {

            dp[i] = max(dp[i - 2] + arr[i], dp[i - 1]);

        }

        else

        {

            dp[i] = max(odd_pos[i - 1], dp[i - 2] + arr[i]);

        }

    }

    printf("%lld\n", dp[n]);



    return 0;

}
// Slower C++ solution:
#pragma GCC optimize("O3")



#include <bits/stdc++.h>



typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

#define F first

#define S second

#define pii pair<int,int>

#define pll pair<ll, ll>

#define vi vector<int>

#define vll vector<ll>

#define vii vector<pii>

#define read(FILE)  freopen(FILE, "r", stdin);

#define out(FILE) freopen(FILE, "w", stdout);

#define clr(x, y) memset(x,y,sizeof(x));

#define IO ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);

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

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

#define forr(i, m, n) for(ll i=m ; i<=n ; i++)

#define endl '\n'

#define pb push_back

#define re return

const int N = 2e5 + 5;

const ll OO = 1e15;

using namespace std;

ll n;

ll arr[N];

ll dp[N][3];



ll solve(ll i, ll c) {

    if (i > n) {

        re c ? -OO : 0;

    }

    ll &ret = dp[i][c];

    if (~ret) re ret;

    ret = -OO;

    if (c) {

        ret = max(ret, solve(i + 1, c - 1));

    }

    ret = max(ret, arr[i] + solve(i + 2, c));

    re ret;

}



int main() {

    cin >> n;

    rep(i, 0, n) {

        cin >> arr[i];

    }

    /*rep(i, 0, N) {

        rep(j, 0, 3) {

            dp[i][j] = OO;

        }

    }*/

    clr(dp, -1);

    cout << solve(0, (n & 1) + 1);



}

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

using namespace std;

#define elif else if

typedef long long ll;

typedef unsigned long long ull;

#define DEBUG(x) cout << (x) << endl

#define TGET(a, b) get<b>(a)



#define MAXN 200100



ll arr[MAXN] = {0};

ll odd_pos[MAXN] = {0};

ll even_pos[MAXN] = {0};



ll dp[MAXN] = {0};



int main()

{

    int n;

    scanf("%d", &n);

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

    {

        scanf("%lld", arr + i);

    }



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

    {

        if (i == 1)

        {

            odd_pos[i] = arr[i];

            even_pos[i + 1] = arr[i + 1];

        }

        else

        {

            odd_pos[i] = arr[i] + odd_pos[i - 2];

            even_pos[i + 1] = arr[i + 1] + even_pos[i - 1];

        }

    }

    // ll ans = even_pos[n-1];

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

    // {

    //     ans = max(ans, odd_pos[n] - arr[i]);

    //     ans = max(ans, (odd_pos[i] - arr[i]) + (even_pos[n - 1] - even_pos[i - 1]));

    //     ans = max(ans, (odd_pos[i] - arr[i]) + arr[i + 1] + (odd_pos[n] - odd_pos[i + 2]));

    // }

    // printf("%ld\n", ans);

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

    {

        if (i % 2)

        {

            dp[i] = max(dp[i - 2] + arr[i], dp[i - 1]);

        }

        else

        {

            dp[i] = max(odd_pos[i - 1], dp[i - 2] + arr[i]);

        }

    }

    printf("%lld\n", dp[n]);



    return 0;

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

#include <stdio.h>

#include <string>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <vector>

#include <set> 

#include <map>

#include <queue>

#include <deque>

#include <stack>

#include <bitset>

#include <iomanip>

using namespace std;

#define assem99 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define ll long long

#define ull unsigned long long

#define ld long double

#define ii pair<int, int>

#define pll pair<ll, ll>

#define vii vector<ii>

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

#define F first

#define S second

#define sz(a) (int)(a).size()

#define ReadFile freopen("input.txt","r",stdin)

#define WriteFile freopen("output.txt","w",stdout)

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

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

const int MOD = 1e9 + 7, N = 2e5 + 5;

const double pi = acos(-1);



ll n, arr[N], dp[N][3];



ll solve(int id, int taken, int skipped)

{

	if (id >= n) return (taken == n / 2) ? 0 : -1e18;

	if (dp[id][skipped] != -1) return dp[id][skipped];

	ll ans = -1e18;

	if (skipped < 2) ans = max(ans, solve(id + 1, taken, skipped + 1));

	ans = max(ans, solve(id + 2, taken + 1, skipped) + arr[id]);

	return dp[id][skipped] = ans;

}



int main()

{ 

	assem99;

	memset(dp, -1, sizeof(dp));

	cin >> n;

	rep(i, 0, n) cin >> arr[i];

	cout << solve(0, 0, 0);



	return 0;

}


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

using namespace std;

#define elif else if

typedef long long ll;

typedef unsigned long long ull;

#define DEBUG(x) cout << (x) << endl

#define TGET(a, b) get<b>(a)



#define MAXN 200100



ll arr[MAXN] = {0};

ll odd_pos[MAXN] = {0};

ll even_pos[MAXN] = {0};



ll dp[MAXN] = {0};



int main()

{

    int n;

    scanf("%d", &n);

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

    {

        scanf("%lld", arr + i);

    }



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

    {

        if (i == 1)

        {

            odd_pos[i] = arr[i];

            even_pos[i + 1] = arr[i + 1];

        }

        else

        {

            odd_pos[i] = arr[i] + odd_pos[i - 2];

            even_pos[i + 1] = arr[i + 1] + even_pos[i - 1];

        }

    }

    // ll ans = even_pos[n-1];

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

    // {

    //     ans = max(ans, odd_pos[n] - arr[i]);

    //     ans = max(ans, (odd_pos[i] - arr[i]) + (even_pos[n - 1] - even_pos[i - 1]));

    //     ans = max(ans, (odd_pos[i] - arr[i]) + arr[i + 1] + (odd_pos[n] - odd_pos[i + 2]));

    // }

    // printf("%ld\n", ans);

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

    {

        if (i % 2)

        {

            dp[i] = max(dp[i - 2] + arr[i], dp[i - 1]);

        }

        else

        {

            dp[i] = max(odd_pos[i - 1], dp[i - 2] + arr[i]);

        }

    }

    printf("%lld\n", dp[n]);



    return 0;

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

using namespace std;

#define ll long long

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

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

#define mset(s,_) memset(s,_,sizeof s)

#define fi first

#define se second

#define pb push_back



template<typename T>

void chmax(T &a,T b){

  if(a<b)a=b;

}



map<int,ll>dp[200010];

ll a[200010],n;



ll dfs(int num,int k){

	if(k<=0) return 0;

  if(num==n&&k==1) return a[num];

  if(k>(n-num)/2+1) return -1e18;

	if(dp[num].count(k)) return dp[num][k];

	if((n-num+1)&1){

		 return dp[num][k]=max(dfs(num+2,k-1)+a[num],max(dfs(num+3,k-1)+a[num+1],dfs(num+4,k-1)+a[num+2]));

	}

	else {

		return dp[num][k]=max(dfs(num+2,k-1)+a[num],dfs(num+3,k-1)+a[num+1]);

	}

}



int main(){

	cin>>n;

	rep(i,1,n) cin>>a[i];

	a[1+n]=-1e18;

	a[2+n]=-1e18;

	a[3+n]=-1e18;

	cout<<dfs(1,n/2)<<'\n';

}



	

	

	

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

#define ll long long

#define ls id << 1

#define rs id << 1 | 1

#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))

#define memarray(array, value) memset(array, value, sizeof(array))

#define pb(x) push_back(x)

#define st(x) (1LL << (x))

#define pii pair<int, int>

#define mp(a, b) make_pair((a), (b))

#define Flush fflush(stdout)

using namespace std;

const int N = 200050;

const int inf = 0x3f3f3f3f;

const ll mod = 998244353LL;

clock_t TIME_START, TIME_END;

void program_end()

{

#ifdef ONLINE

    printf("\nTime used: %.6lf(s)\n", ((double)TIME_END - TIME_START) / CLOCKS_PER_SEC);

    system("pause");

#endif

}

ll dp[N];

ll a[N];

ll sum[N];

int n;



void solve()

{

    scanf("%d", &n);

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

        scanf("%lld", &a[i]);

    sum[1] = a[1];

    for (int i = 3; i <= n; i += 2)

        sum[i] = sum[i - 2] + a[i];

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

    {

        if (i & 1)

            dp[i] = max(dp[i - 1], dp[i - 2] + a[i]);

        else

            dp[i] = max(sum[i - 1], dp[i - 2] + a[i]);

    }

    printf("%lld\n", dp[n]);

}



int main()

{

    TIME_START = clock();

    int Test = 1;

    // cin >> Test;

    while (Test--)

        solve();

    TIME_END = clock();

    program_end();

    return 0;

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

using namespace std;

#define ll long long

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

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

#define mset(s,_) memset(s,_,sizeof s)

#define fi first

#define se second

#define pb push_back



template<typename T>

void chmax(T &a,T b){

  if(a<b)a=b;

}



map<int,ll>dp[200010];

ll a[200010],n;



ll dfs(int num,int k){

	if(k<=0) return 0;

  if(num==n&&k==1) return a[num];

  if(k>(n-num)/2+1) return -1e18;

	if(dp[num].count(k)) return dp[num][k];

	if((n-num+1)&1){

		 return dp[num][k]=max(dfs(num+2,k-1)+a[num],max(dfs(num+3,k-1)+a[num+1],dfs(num+4,k-1)+a[num+2]));

	}

	else {

		return dp[num][k]=max(dfs(num+2,k-1)+a[num],dfs(num+3,k-1)+a[num+1]);

	}

}



int main(){

	cin>>n;

	rep(i,1,n) cin>>a[i];

	a[1+n]=-1e18;

	a[2+n]=-1e18;

	a[3+n]=-1e18;

	cout<<dfs(1,n/2)<<'\n';

}



	

	

	

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

using namespace std;

typedef long long ll;

const ll mx = 2e5+10;

ll dp[mx],arr[mx];

int main()

{

    ll n ;

    cin>>n;

    ll sum=0;

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

    {

        cin>>arr[i];

        if(i%2!=0)

            sum+=arr[i];

        if(i!=1)

        {

            if(i%2!=0)

                dp[i]=max(dp[i-2]+arr[i],dp[i-1]);

            else

                dp[i]=max(dp[i-2]+arr[i],sum);

        }

    }

    cout<<dp[n]<<endl;

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

#define MOD 1000000007

#define INF 1061109567

#define pb push_back

#define in(s) freopen(s,"r",stdin);

#define out(s) freopen(s,"w",stdout);

#define fi first

#define se second

#define bw(i,r,l) for (int i=r-1;i>=l;i--)

#define fw(i,l,r) for (int i=l;i<r;i++)

#define fa(i,x) for (auto i:x)

using namespace std;

const int N=1e5+5;

int n,L,q,x[N],sp[N][20];

int get(int x,int y) {

	int ans=1;

	bw (i,18,0) if (sp[x][i]!=-1&&sp[x][i]<y) x=sp[x][i],ans+=(1<<i);

	return ans;

}

signed main() {

	//in("aome.inp");

	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin>>n;

	fw (i,0,n) cin>>x[i];

	cin>>L>>q;

	memset(sp,-1,sizeof(sp));

	fw (i,0,n) sp[i][0]=upper_bound(x,x+n,x[i]+L)-x-1;

	fw (j,1,18) fw (i,0,n) if (sp[i][j-1]!=-1) sp[i][j]=sp[sp[i][j-1]][j-1];

	while (q--) {

		int a,b; 

		cin>>a>>b;

		if (a>b) swap(a,b);

		cout<<get(a-1,b-1)<<"\n";

	}

	return 0;

}

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



using namespace std;

#define int long long

#define pb push_back

int n, q;



long long x[100005], l, y[100005][20];

vector<int> vec;



signed main() {

    cin.tie(0), ios::sync_with_stdio(0);

    cin >> n;

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

        cin >> x[i];

        vec.pb(x[i]);

    }

    vec.pb(-1);

    sort(vec.begin(), vec.end());

    cin >> l;

    cin >> q;

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

        int it = upper_bound(vec.begin(), vec.end(), x[i] + l) - vec.begin() - 1;

        y[i][0] = it;

    }

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

        for(int j = 1;j <= n; j++)

            y[j][i] = y[y[j][i - 1]][i - 1];

    }

    while(q--){

        int a, b, sum = 0;

        cin >> a >> b;

        if(a == b){

            cout << sum << "\n";

            continue;

        }

        if(b < a)

            swap(a, b);

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

            if(y[a][i] < b){

                a = y[a][i];

                sum += (1 << i);

            }

        }

        sum++;

        cout << sum << "\n";

    }

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

#define MOD 1000000007

#define INF 1061109567

#define pb push_back

#define in(s) freopen(s,"r",stdin);

#define out(s) freopen(s,"w",stdout);

#define fi first

#define se second

#define bw(i,r,l) for (int i=r-1;i>=l;i--)

#define fw(i,l,r) for (int i=l;i<r;i++)

#define fa(i,x) for (auto i:x)

using namespace std;

const int N=1e5+5;

int n,L,q,x[N],sp[N][20];

int get(int x,int y) {

	int ans=1;

	bw (i,18,0) if (sp[x][i]!=-1&&sp[x][i]<y) x=sp[x][i],ans+=(1<<i);

	return ans;

}

signed main() {

	//in("aome.inp");

	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin>>n;

	fw (i,0,n) cin>>x[i];

	cin>>L>>q;

	memset(sp,-1,sizeof(sp));

	fw (i,0,n) sp[i][0]=upper_bound(x,x+n,x[i]+L)-x-1;

	fw (j,1,18) fw (i,0,n) if (sp[i][j-1]!=-1) sp[i][j]=sp[sp[i][j-1]][j-1];

	while (q--) {

		int a,b; 

		cin>>a>>b;

		if (a>b) swap(a,b);

		cout<<get(a-1,b-1)<<"\n";

	}

	return 0;

}

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

#include<cstdio>

using namespace std;

const int magic=307;

int n,x[111111],l,q,a,b,nxt[111111],bignxt[111111],pos,ans;

int main()

{

	scanf("%d",&n);

	for (int i=1;i<=n;i++) scanf("%d",&x[i]);

	scanf("%d",&l);

	pos=n;

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

	{

		while(pos>=1 && x[pos]-x[i]>l) pos--;

		nxt[i]=pos;

	}

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

	{

		pos=i;

		for (int j=1;j<=magic;j++)

		{

			pos=nxt[pos];

		}

		bignxt[i]=pos;

	}

	scanf("%d",&q);

	while(q--)

	{

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

		if (a>b) swap(a,b);

		ans=0;

		while(bignxt[a]<b) 

		{

			ans+=magic;

			a=bignxt[a];

		}

		while(nxt[a]<b) 

		{

			ans++;

			a=nxt[a];

		}

		if (a!=b) ans++;

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

	}

	return 0;

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

#define MOD 1000000007

#define INF 1061109567

#define pb push_back

#define in(s) freopen(s,"r",stdin);

#define out(s) freopen(s,"w",stdout);

#define fi first

#define se second

#define bw(i,r,l) for (int i=r-1;i>=l;i--)

#define fw(i,l,r) for (int i=l;i<r;i++)

#define fa(i,x) for (auto i:x)

using namespace std;

const int N=1e5+5;

int n,L,q,x[N],sp[N][20];

int get(int x,int y) {

	int ans=1;

	bw (i,18,0) if (sp[x][i]!=-1&&sp[x][i]<y) x=sp[x][i],ans+=(1<<i);

	return ans;

}

signed main() {

	//in("aome.inp");

	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin>>n;

	fw (i,0,n) cin>>x[i];

	cin>>L>>q;

	memset(sp,-1,sizeof(sp));

	fw (i,0,n) sp[i][0]=upper_bound(x,x+n,x[i]+L)-x-1;

	fw (j,1,18) fw (i,0,n) if (sp[i][j-1]!=-1) sp[i][j]=sp[sp[i][j-1]][j-1];

	while (q--) {

		int a,b; 

		cin>>a>>b;

		if (a>b) swap(a,b);

		cout<<get(a-1,b-1)<<"\n";

	}

	return 0;

}

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

using namespace std;



int p[100001][17],a[100001];

int A,B;



bool check(int x){

	int tmp=B,stp=0;

	while(x){

		if(x&1)	tmp=p[tmp][stp];

		stp++;

		x>>=1;

	}

	return tmp<=A;



}



int main(){

	ios_base::sync_with_stdio(0);

	cin.tie(0);

	int n,L,k;

	cin>>n;

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

		cin>>a[i];

	int tmp=n;

	cin>>L>>k;

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

		while(tmp>0&&a[i]-a[tmp]<=L)

			tmp--;

		p[i][0]=tmp+1;

	}

	for(int j=1;j<=16;j++)

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

			p[i][j]=p[p[i][j-1]][j-1];

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

		cin>>A>>B;

		if(A>B)	swap(A,B);

		int l=0,r=100000;

		while(l<r){

			int mid=(l+r)/2;

			if(check(mid))

				r=mid;

			else

				l=mid+1;

		}

		cout<<l<<'\n';

	}

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

#define MOD 1000000007

#define INF 1061109567

#define pb push_back

#define in(s) freopen(s,"r",stdin);

#define out(s) freopen(s,"w",stdout);

#define fi first

#define se second

#define bw(i,r,l) for (int i=r-1;i>=l;i--)

#define fw(i,l,r) for (int i=l;i<r;i++)

#define fa(i,x) for (auto i:x)

using namespace std;

const int N=1e5+5;

int n,L,q,x[N],sp[N][20];

int get(int x,int y) {

	int ans=1;

	bw (i,18,0) if (sp[x][i]!=-1&&sp[x][i]<y) x=sp[x][i],ans+=(1<<i);

	return ans;

}

signed main() {

	//in("aome.inp");

	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin>>n;

	fw (i,0,n) cin>>x[i];

	cin>>L>>q;

	memset(sp,-1,sizeof(sp));

	fw (i,0,n) sp[i][0]=upper_bound(x,x+n,x[i]+L)-x-1;

	fw (j,1,18) fw (i,0,n) if (sp[i][j-1]!=-1) sp[i][j]=sp[sp[i][j-1]][j-1];

	while (q--) {

		int a,b; 

		cin>>a>>b;

		if (a>b) swap(a,b);

		cout<<get(a-1,b-1)<<"\n";

	}

	return 0;

}

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

  mail: mleautomaton@foxmail.com

  author: MLEAutoMaton

  This Code is made by MLEAutoMaton

*/

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<iostream>

using namespace std;

#define ll long long

#define REP(a,b,c) for(int a=b;a<=c;a++)

#define re register

#define int ll

#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)

inline int gi(){

	int f=1,sum=0;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}

	return f*sum;

}

const int N=100010;

int x[N],n,L,nxt[N][20];

signed main(){

	n=gi();

	for(int i=1;i<=n;i++)x[i]=gi();

	L=gi();

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

		int l=i+1,r=n,ans=i;

		while(l<=r){

			int mid=(l+r)>>1;

			if(x[mid]-x[i]<=L){ans=mid;l=mid+1;}

			else r=mid-1;

		}

		nxt[i][0]=ans;

	}

	for(int j=1;j<=18;j++)

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

			nxt[i][j]=nxt[nxt[i][j-1]][j-1];

	int q=gi();

	while(q--){

		int a=gi(),b=gi();if(a>b)swap(a,b);

		int ans=0;

		for(int i=18;~i;i--)

			if(nxt[a][i]<b){a=nxt[a][i];ans+=1ll<<i;}

		printf("%lld\n",ans+1);

	}

	return 0;

}



//ORz hyj