LCA

using namespace std;

#include <iostream>
#include <deque>
#include <vector>

struct node
{
    int data;
    struct node * left;
    struct node * right;
    struct node * parent;
    bool visited;
};

struct node * insert(int, int);
void postorder(struct node *);
struct node * getNode(int);
struct node * findZone(struct node *, struct node *);

deque <int> d;
vector <struct node *> v;
int * in, * post, n;

int main(void)
{
    int q, z1, z2, num;

    cin >> n;

    in = new int[n];
    post = new int[n];

    for(int i=0; i<n; i++)
    {
        cin >> num;
        d.push_front(num);
    }

    for(int i=0; i<n; i++)
    {
        cin >> in[i];
    }

    struct node * root = insert(0, n-1);
    if(root)
    {
        root->parent = NULL;
        root->visited = false;
    }
    postorder(root);

    cin >> q;

    for(int i = 0; i<q; i++)
    {
        cin >> z1 >> z2;
        struct node * z11 = getNode(z1);
        struct node * z22 = getNode(z2);
        if(z11 == z22)
        {
            cout << z11->data << endl;
        }
        else
        {
            struct node * z = findZone(z11, z22);
            if(!z)
              cout << root->data << endl;
            else
              cout << z->data << endl;
        }
        for(int j=0; j<n; j++)
          v.at(j)->visited = false;
    }


    delete [] in;
    delete [] post;
    v.clear();

    return 0;
}

struct node * insert(int begin, int end)
{
    if(begin > end)
      return NULL;

    struct node * root = new struct node;
    root->data = d.back();
    root->left = NULL;
    root->right = NULL;

    if(begin == end)
    {
        d.pop_back();
        return root;
    }

    int i = begin;
    while(in[i] != d.back() && i < n)
      i++;

    d.pop_back();

    root->left = insert(begin, i-1);
    if(root->left)
    {
        root->left->parent = root;
        root->left->visited = false;
    }

    root->right = insert(i+1, end);
    if(root->right)
    {
        root->right->parent = root;
        root->right->visited = false;
    }

    return root;
}

void postorder(struct node * root)
{
    if(!root)
      return;
    postorder(root->left);
    postorder(root->right);
    v.push_back(root);
}

struct node * getNode(int key)
{
    for(int i=0; i<n; i++)
    {
        if(v.at(i)->data == key)
          return v.at(i);
    }
    return NULL;
}

struct node * findZone(struct node * z1, struct node * z2)
{
    while(z1 || z2)
    {
        if(z1)
        {
            if(z1->visited)
              return z1;
            z1->visited = true;
            z1 = z1->parent;
        }
        if(z2)
        {
            if(z2->visited)
              return z2;
            z2->visited = true;
            z2 = z2->parent;
        }
    }
    return NULL;
}