Lịch trực (Duty Schedule)

Phiên bản: Phước Hưng OJ

Đề bài

Trong một đợt hoạt động của trường có $N$ nhóm học sinh tham gia trực phòng máy. Thời gian được chia thành các thời điểm nguyên dương $1,2,3,\ldots$. Nhóm thứ $i$ trực liên tục từ thời điểm $L_i$ đến thời điểm $R_i$, kể cả hai đầu mút.

Tại thời điểm $t$, số nhóm đang trực là số chỉ số $i$ thỏa mãn $L_i\le t\le R_i$.

Hãy xác định:

• $M$ — số nhóm trực đồng thời lớn nhất;
• $P$ — thời điểm nhỏ nhất mà có đúng $M$ nhóm đang trực;
• $C$ — số thời điểm nguyên dương có đúng $M$ nhóm đang trực.

Input

• Dòng đầu chứa số nguyên dương $N$.
• Trong $N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên dương $L_i,R_i$ với $L_i\le R_i$.

Output

In ra ba số nguyên $M,P,C$ trên cùng một dòng, cách nhau bởi một dấu cách.

Subtask

• Subtask 1 (30%): $1\le N\le 10^3$, $1\le L_i\le R_i\le 10^5$.
• Subtask 2 (30%): $1\le N\le 2\times 10^4$, $1\le L_i\le R_i\le 10^6$.
• Subtask 3 (40%): $1\le N\le 2\times 10^5$, $1\le L_i\le R_i\le 10^9$.

Ví dụ

Ví dụ 1

Input

4
1 4
3 6
4 4
8 10

Output

3 4 1

Giải thích

Tại thời điểm $4$ có ba nhóm cùng trực và không có thời điểm nào khác đạt mức này.

Ví dụ 2

Input

3
2 5
2 5
2 5

Output

3 2 4

Giải thích

Từ thời điểm $2$ đến $5$ đều có ba nhóm cùng trực, nên có $4$ thời điểm đạt mức lớn nhất.

Ví dụ 3

Input

3
1 2
4 5
7 7

Output

1 1 5

Giải thích

Không có hai nhóm nào trực cùng lúc. Có tổng cộng $5$ thời điểm thuộc các ca trực và mỗi thời điểm có đúng một nhóm trực.