976 C. Nested Segments

You are given a sequence a₁, a₂, ..., a_n of one-dimensional segments numbered 1 through n. Your task is to find two distinct indices i and j such that segment a_i lies within segment a_j.

Segment [l₁, r₁] lies within segment [l₂, r₂] iff l₁ ≥ l₂ and r₁ ≤ r₂.

Print indices i and j. If there are multiple answers, print any of them. If no answer exists, print -1 -1.

Input

The first line contains one integer n (1 ≤ n ≤ 3·10⁵) — the number of segments.

Each of the next n lines contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ 10⁹) — the i-th segment.

Output

Print two distinct indices i and j such that segment a_i lies within segment a_j. If there are multiple answers, print any of them. If no answer exists, print -1 -1.

Examples

Input

Copy

Output

Copy

2 1

Input

Copy

Output

Copy

-1 -1
寻找是否存在一个段包含在另一个段里，输出段的编号

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <vector>

#include <queue>

#include <stack>

#include <cstdlib>

#include <iomanip>

#include <cmath>

#include <cassert>

#include <ctime>

#include <map>

#include <set>

using namespace std;

#pragma comment(linker, "/stck:1024000000,1024000000")

#define lowbit(x) (x&(-x))

#define max(x,y) (x>=y?x:y)

#define min(x,y) (x<=y?x:y)

#define MAX 100000000000000000

#define MOD 1000000007

#define pi acos(-1.0)

#define ei exp(1)

#define PI 3.1415926535897932384626433832

#define ios() ios::sync_with_stdio(true)

#define INF 0x3f3f3f3f

#define mem(a) ((a,0,sizeof(a)))

typedef long long ll;

struct node

{

    int x,y,z;

    bool operator<(const node &a)

    {

        return a.x==x?a.y<y:a.x>x;

    }

}e[];

int n;

int main()

{

    scanf("%d",&n);

    for(int i=;i<n;i++)

    {

        scanf("%d%d",&e[i].x,&e[i].y);

        e[i].z=i;

    }

    sort(e,e+n);

    for(int i=;i<n-;i++)

    {

        if(e[i].x<=e[i+].x && e[i].y>=e[i+].y)

        {

            printf("%d %d\n",e[i+].z+,e[i].z+);

            return ;

        }

    }

    printf("-1 -1\n");

    return ;

}

巴特西

976 C. Nested Segments

最新文章

热门文章