만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

유일한 호수

면접 대비

시간 제한1초메모리 제한1024 MB

요약
x와 y가 모두 더 큰 점으로만 이동하는 가장 긴 점 순서의 길이와, 그런 가장 긴 순서의 개수를 10^9+7로 나눈 나머지로 구합니다.
난이도

보통10점 중 6점

유형
동적 계획법, 정렬, 세그먼트 트리
정답자
아직 제출이 없습니다

문제

슬론 미르코는 연잎 nn개가 떠 있는 큰 호수 옆에 산다. 호수를 좌표평면으로 생각하면, 각 연잎은 정수 좌표를 가진 점에 놓여 있다.

미르코는 매일 아침 연잎에서 연잎으로 뛰며 운동을 한다. 이유는 본인만 알고 있지만, 미르코는 현재 연잎에서 두 좌표가 모두 현재 연잎의 좌표보다 큰 연잎으로만 뛸 수 있다. 즉 (x1,y1)(x_1, y_1) 연잎에서 (x2,y2)(x_2, y_2) 연잎으로 뛸 수 있는 조건은 x2>x1x_2 > x_1이고 y2>y1y_2 > y_1인 경우뿐이다. 첫 연잎은 미르코가 직접 고른다.

미르코는 운동이 가능한 한 오래 이어지기를 바라고, 매일 다른 방식으로 뛰고 싶어 한다.

주어진 연잎 배치에서 미르코의 조건을 만족하는 연잎 순서 중 가장 긴 것의 길이를 구하라. 또한 그러한 가장 긴 순서의 개수도 구해야 한다. 개수가 매우 클 수 있으므로 1 000 000 0071\,000\,000\,007로 나눈 나머지만 출력한다.

입력

첫 줄에 문제문의 자연수 nn (1≤n≤300 0001 \le n \le 300\,000)이 주어진다.

이어지는 nn개의 줄에는 각각 연잎 하나의 좌표를 나타내는 두 정수 xx와 yy (0≤x,y≤1090 \le x, y \le 10^9)가 주어진다.

서로 다른 두 연잎이 같은 좌표에 놓이지 않는다.

출력

첫 줄에 문제에서 설명한 대로 미르코가 뛸 수 있는 연잎 순서 중 가장 긴 것의 길이를 출력한다.

둘째 줄에는 가장 긴 순서의 개수를 1 000 000 0071\,000\,000\,007로 나눈 나머지를 출력한다.

예제3

  1. 예제 1

    입력
    4
    1 1
    4 2
    2 3
    3 4
    
    예상 출력
    3
    1
    
  2. 예제 2

    입력
    6
    1 3
    2 2
    3 1
    5 3
    4 4
    3 5
    
    예상 출력
    2
    7
    
  3. 예제 3

    입력
    11
    8 6
    7 4
    5 4
    5 1
    5 6
    6 2
    3 2
    4 3
    4 5
    3 5
    2 4
    
    예상 출력
    4
    3