/*------------------------------------------------------------------------------
 * problem011.c: Find LCA in BST
**----------------------------------------------------------------------------*/

/* Copyright (c) 2009 Peter Bui. All Rights Reserved.
 *
 * Peter Bui <pbui@cse.nd.edu>
 *
**------------------------------------------------------------------------------
 * Includes
**----------------------------------------------------------------------------*/

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*------------------------------------------------------------------------------
 * Data Structures
**----------------------------------------------------------------------------*/

struct IntNode {
    int	value;
    struct IntNode *left;
    struct IntNode *right;
};

/*------------------------------------------------------------------------------
 * Functions
**----------------------------------------------------------------------------*/

static struct IntNode *
create_node(const int v)
{
    struct IntNode *n;

    n = malloc(sizeof(struct IntNode));
    n->left  = n->right = NULL;
    n->value = v;

    return (n);
}

static void
insert_node(struct IntNode **n, const int v)
{
    if (*n == NULL)
	*n = create_node(v);
    else if (v < (*n)->value)
	insert_node(&((*n)->left), v);
    else
	insert_node(&((*n)->right), v);
}

static int
find_lca(struct IntNode *n, int v0, int v1)
{
    int v;

    while (n != NULL) {
	v = n->value;

	if (v > v0 && v > v1)
	    n = n->left;
	else if (v < v0 && v < v1)
	    n = n->right;
	else
	    return (v);
    }

    return (-1);
}

static void
free_tree(struct IntNode **n)
{
    if (*n) {
	if ((*n)->left) 
	    free_tree(&((*n)->left));
	if ((*n)->right)
	    free_tree(&((*n)->right));
	free(*n);
	*n = NULL;
    }
}

/*------------------------------------------------------------------------------
 * Main Execution
**----------------------------------------------------------------------------*/

int
main(int argc, char* argv[]) 
{
    struct IntNode *root = NULL;
    int i, v, v0, v1, nnodes, npairs;
    int first_pass = 1;

    while (scanf("%d", &nnodes) != EOF) {
	if (nnodes < 0) break;

	if (!first_pass)
	    putchar('\n');

	for (i = 0; i < nnodes; i++) {
	    scanf("%d", &v);
	    insert_node(&root, v);
	}

	scanf("%d", &npairs);
	for (i = 0; i < npairs; i++) {
	    scanf("%d %d", &v0, &v1);
	    printf("%d\n", find_lca(root, v0, v1));
	}

	free_tree(&root);
	first_pass = 0;
    }

    return (EXIT_SUCCESS);
}

/*------------------------------------------------------------------------------
 * vim: sts=4 sw=4 ts=8 ft=c
**----------------------------------------------------------------------------*/