#include <iostream>
#include <stack>
#include <limits>
#include <algorithm>
using namespace std;

struct node
{
    int l,r, Min, best_id;
    node * lp, *rp;
    node () {};
    node(int x, int val, int id): l(x), r(x), Min (val), lp(NULL), rp(NULL), best_id(id) {};
    node (node * left, node *right): lp(left), rp(right), l(left->l), r(right->r)
    {
        if (left->Min < right->Min)
        {
            Min=left->Min;
            best_id= left->best_id;
        }
        else
        {
            Min=right->Min;
            best_id= right->best_id;
        }
    }
};

struct interval
{
    int l,r,id;
};

node * init(interval * tab, int n)
{
    auto f=[](interval a,interval b) {return a.l < b.l;};
    sort(tab,tab+n,f);
    stack <node *> Q,P;
    node * tmp1, *tmp2;
    for (int i=0;i<n;i++)
        Q.push(new node(tab[i].l, tab[i].r , tab[i].id));
    while (true)
    {
        if (Q.size()==1) return Q.top();
        while(Q.size()>1)
        {
            tmp2=Q.top();
            Q.pop();
            tmp1=Q.top();
            Q.pop();
            P.push(new node(tmp1,tmp2));
        }
        if (!Q.empty())
        {
            P.push(Q.top());
            Q.pop();
        }

        if(P.size()==1) return P.top();
        while(P.size()>1)
        {
            tmp1=P.top();
            P.pop();
            tmp2=P.top();
            P.pop();
            Q.push(new node(tmp1,tmp2));
        }
        if (!P.empty())
        {
            Q.push(P.top());
            P.pop();
        }
    }
}

pair<int,int> get_min(node * root, int ql)
{
    if (ql > root->r)
        return {INT_MAX,-1};

    if (ql <= root->l)
        return {root->Min, root->best_id};

    pair <int,int> left, right;
    left=get_min(root->lp,ql);
    right=get_min(root->rp,ql);

    if (left.first < right.first)
        return left;
    return right;
}

int main ()
{
    ios_base::sync_with_stdio(false);
    int n,l,r;
    node * root;
    cin >> n;
    interval tab[n];
    for (int i=0;i<n;i++)
    {
        tab[i].id=i;
        cin >> tab[i].l >> tab[i].r;
    }
    root=init(tab,n);

    cout << "intervals: " << endl;
    for (int i=0;i<n;i++)
    {
        cout << "(id: " << tab[i].id << ") " << tab[i].l << " - " << tab[i].r << endl;
    }
    cout << endl;

    for (int i=0;i<n;i++)
        cout << "best for " << tab[i].id << "  :  " << get_min(root, tab[i].r).second << endl;
}