记录编号	308819	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2012]开车旅行	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	3.007 s
提交时间	2016-09-18 18:05:03	内存使用	35.88 MiB

//KZNS
#include <cstdio>
#include <set>
#include <cmath>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;
#define Nmax 100003
typedef pair<int, int> pr;
typedef set<pr>::iterator sti;
typedef long long LL;
inline int loog(int x) {
    if (x <= 1)
        return 0;
    int u = 1;
    for (int i = 1; true; i++)
        if (x <= (u<<=1))
            return i;
}
inline int input() {
	int ans = 0;
	int f = 1;
	char c = getchar();
	while (!('0' <= c && c <= '9')) {
		if (c == '-')
            f = -1;
        c = getchar();
	}
	while ('0' <= c && c <= '9')
		ans = ans * 10 + c - '0', c = getchar();
	return ans * f;
}
int N, M;
int H[Nmax];
int gt[Nmax][2] = {0};//x, 0 = max_two, 1 = max_one
LL V[Nmax][2] = {0};
int pg[Nmax] = {0};
int jg[Nmax][17];//n, 2^k;
LL jv[Nmax][17] = {0};
LL ja[Nmax][17] = {0};
void rin() {
    N = input();
    for (int i = 1; i <= N; i++)
        H[i] = input();
}
void fir() {
    set<pr> st;
    st.insert(make_pair(H[N], N));
    sti uu;
    pr u1, u2;
    for (int i = N-1; i >= 1; i--) {
        st.insert(make_pair(H[i], i));
        uu = st.lower_bound(make_pair(H[i], i));
        if (uu != st.begin()) {
            uu--;
            u1 = *uu;
            uu++;
        }
        else
            u1.second = 0;
        if (++uu != st.end())
            u2 = *uu;
        else
            u2.second = 0;
        uu--;
        if (u2.second && (!u1.second || u2.first - H[i] < H[i] - u1.first)) {
            gt[i][1] = u2.second;
            V[i][1] = u2.first - H[i];
            uu++;
            uu++;
            if (uu != st.end())
                u2 = *uu;
            else
                u2.second = 0;
        }
        else {
            gt[i][1] = u1.second;
            V[i][1] = H[i] - u1.first;
            uu--;
            if (uu != st.begin()) {
                uu--;
                u1 = *uu;
            }
            else
                u1.second = 0;
        }
        if (u2.second && (!u1.second || u2.first - H[i] < H[i] - u1.first)) {
            gt[i][0] = u2.second;
            V[i][0] = u2.first - H[i];
        }
        else if (u1.second) {
            gt[i][0] = u1.second;
            V[i][0] = H[i] - u1.first;
        }
        pg[i] = max(pg[gt[i][0]], pg[gt[i][1]]) + 1;
    }
    
    for (int i = 1; i <= N; i++) {
        jg[i][0] = gt[i][0];
        jv[i][0] = V[i][0];
        ja[i][0] = V[i][0];
    }
    for (int i = 1; i <= N; i++) {
        jg[i][1] = gt[ gt[i][0] ][1];
        jv[i][1] = V[i][0] + V[ gt[i][0] ][1];
        ja[i][1] = V[i][0];
    }
    for (int k = 2; k < 17; k++) {
        for (int i = 1; i <= N && loog(pg[i]) >= k; i++) {
            jg[i][k] = jg[ jg[i][k-1] ][k-1];
            jv[i][k] = jv[i][k-1] + jv[ jg[i][k-1] ][k-1];
            ja[i][k] = ja[i][k-1] + ja[ jg[i][k-1] ][k-1];
        }
    }
    
}
int X0;
bool ud[Nmax] = {false};
int ox, oa = 0x7fffffff, ob = 0;
void cp(int x, int a, int b) {
    ud[x] = true;
    if (ob == 0) {
        if (b == 0 && a < oa) {
            oa = a;
            ox = x;
        }
        else if (b) {
            ox = x;
            oa = a;
            ob = b;
        }
    }
    else if (b == 0) {
        return;
    }
    else if ((double)a / b < (double)oa / ob) {
        ox = x;
        oa = a;
        ob = b;
    }
}
void kz(int x) {
    int t = x;
    int sm = 0, a = 0;
    for (int k = loog(pg[x]); k >= 0; k--) {
        if (jg[x][k] && sm + jv[x][k] <= X0) {
            sm += jv[x][k];
            a += ja[x][k];
            x = jg[x][k];
        }
    }
    cp(t, a, sm - a);
}
void mission1() {
    X0 = input();
    for (int i = 1; i <= N; i++)
        kz(i);
    printf("%d\n", ox);
}
void mission2() {
    M = input();
    int S, X;
    LL SMG, AG;
    while (M--) {
        S = input();
        X = input();
        SMG = 0;
        AG = 0;
        for (int k = loog(pg[S]); k >= 0; k--) {
            if (jg[S][k] && SMG + jv[S][k] <= X) {
                SMG += jv[S][k];
                AG += ja[S][k];
                S = jg[S][k];
            }
        }
        printf("%lld %lld\n", AG, SMG - AG);
    }
}
int main() {
	freopen("drive.in", "r", stdin);
	freopen("drive.out", "w", stdout);
	rin();
	fir();
	mission1();
	mission2();
	return 0;
}
//UBWH