#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    struct tnode{
        int l,r;
        int sum;//segment sum
        int val;//segment max
    };
    //vector<int> a;//input
    vector<struct tnode> tree;
    void buildtree(int no,int l,int r,vector<int> &a){
        tree[no].l=l;
        tree[no].r=r;
        int mid=(l+r)/2;
        if (l==r){
            //segment max
            tree[no].val=a[l];
            //segment sum
            //tree[no].sum=a[l];
        }
        else{
            buildtree(no*2,l,mid,a);
            buildtree(no*2+1,mid+1,r,a);
            // segment max
            tree[no].val=max(tree[no*2].val,tree[no*2+1].val);
            // segment sum
            //tree[no].sum=tree[no*2].sum+tree[no*2+1].sum;
        }
        return;
    }
    /*
    //更新区间和
    void update0(int no,int lr, int val) {
        if (tree[no].l==lr && tree[no].r==lr){
            tree[no].sum=val;
            return;
        }

        int mid=(tree[no].l+tree[no].r)/2;
        if (lr>mid){
            update0(no*2+1,lr,val);
        }
        else{
            update0(no*2,lr,val);
        }
        tree[no].sum=tree[no*2].sum+tree[no*2+1].sum;
    }

    void update(int index, int val) {
        update0(1,index+1,val);
    }

    //查找区间和
    int query(int no,int l, int r) {
        if (tree[no].l==l && tree[no].r==r)
            return tree[no].sum;

        int mid=(tree[no].l+tree[no].r)/2;
        if (l>mid)
            return query(no*2+1,l,r);
        else if (r<=mid)
            return query(no*2,l,r);
        else
            return query(no*2,l,mid)+query(no*2+1,mid+1,r);
    }
    */
    //查找区间大于v的最左侧位置
    int query(int no,int v, int pos,int l, int r) {
        if (tree[no].val<=v)
            return -1;
        if (l==r)
            return l;

        int mid=(l+r)/2;
        if (pos<=mid){
            int res=query(no*2,v,pos,l,mid);
            if (res>=0)
                return res;
        }
        return query(no*2+1,v,pos,mid+1,r);
    }

    vector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
        int n=heights.size();
        tree.resize(4*n+1);
        buildtree(1,0,n-1,heights);
        int qn=queries.size();
        vector<int> res(qn);
        for (int i=0;i<qn;i++){
            int a=queries[i][0];
            int b=queries[i][1];
            if (a>b) swap(a,b);
            if (a==b){
                res[i]=a;
            }else if (heights[b]>heights[a]){
                res[i]=b;
            }else{
                res[i]=query(1,heights[a],b+1,0,n-1);
            }
        }
        return res;
    }
};
int main()
{
    Solution sol;
    vector<int> heights={3,1,2,4,5};
    vector<vector<int>> queries={{0,1},{1,0}};
    vector<int> res=sol.leftmostBuildingQueries(heights,queries);
    for (auto r:res){
        cout << r << " ";
    }
    cout << endl;
    return 0;
}