Trồng hoa

Time limit: 1.0s , Memory limit: 256M , Points: 100 (partial)

Nông dân Flowar dự tính xây dựng một khu vườn trồng hoa. Điều làm Flowar phải đau đầu là những luật lệ trồng hoa kỳ lạ tại đất nước của cô ta.

Flowar dự tính trồng các bông hoa dọc theo hàng rào đường thẳng, có tổng cộng $n$ $n$ vị trí để trồng hoa. Sau bao ngày nỗ lực, cô đã trồng được tổng cộng $n$ $n$ bông hoa sao cho mỗi vị trí thứ $i$ $i$ $(0 \le i < n)$ $(0 \leq i < n)$ đều có chính xác một bông hoa. Tuy nhiên, đất nước mà cô đang sinh sống có những luật lệ trồng hoa rất kỳ lạ. Có tổng cộng $n$ $n$ luật, luật thứ $i$ $i$ $(0 \le i < n)$ $(0 \leq i < n)$ bao gồm hai số nguyên $l_i$ $l_{i}$ và $r_i$ $r_{i}$ , yêu cầu rằng nếu tại vị trí $i$ $i$ có trồng hoa thì $l_i$ $l_{i}$ vị trí ngay bên trái và $r_i$ $r_{i}$ vị trí ngay bên phải không được trồng bất cứ bông hoa nào $($ $($ lưu ý rằng nếu có ít hơn $l_i$ $l_{i}$ vị trí ở bên trái hoặc ít hơn $r_i$ $r_{i}$ vị trí ở bên phải thì tất cả các vị trí đó vẫn không được trồng hoa $)$ $)$ .

Flowar không muốn mình phải chịu phạt vì vi phạm luật lệ trồng hoa, cô muốn cắt bỏ bớt một vài bông hoa $($ $($ có thể không bỏ bất cứ bông hoa nào $)$ $)$ sao cho khu vườn của cô đều thỏa mãn tất cả $n$ $n$ luật lệ. Ngoài ra, Flowar muốn số lượng bông hoa còn lại càng nhiều càng tốt.

Là một người bạn của Flowar, bạn hãy giúp cô tính số lượng bông hoa nhiều nhất còn lại sau khi cắt bỏ một số bông hoa để thỏa mãn tất cả các luật lệ.

Input

Dòng đầu tiên chứa số nguyên $n$ $n$ $(1 \le n \le 2 \times 10^5)$ $(1 \leq n \leq 2 \times 10^{5})$ .
$n$ $n$ dòng tiếp theo, dòng thứ $i$ $i$ chứa hai số nguyên $l_i$ $l_{i}$ và $r_i$ $r_{i}$ $(0 \le l_i,r_i \le n)$ $(0 \leq l_{i}, r_{i} \leq n)$ .

Output

In ra số lượng bông hoa nhiều nhất còn lại.

Examples

Sample Input 1

Copy

Sample Output 1

Copy

Sample Input 2

Copy

Sample Output 2

Copy

Scoring

Subtask $1$ $1$ $-$ $-$ $20$ $20$ điểm: $l_i=l_j=r_i=r_j$ $l_{i} = l_{j} = r_{i} = r_{j}$ với mọi $0 \le i,j < n$ $0 \leq i, j < n$
Subtask $2$ $2$ $-$ $-$ $20$ $20$ điểm: $r_i=0$ $r_{i} = 0$ với mọi $i$ $i$
Subtask $3$ $3$ $-$ $-$ $20$ $20$ điểm: $n \le 1000$ $n \leq 1000$
Subtask $4$ $4$ $-$ $-$ $20$ $20$ điểm: $l_i,r_i \le 2$ $l_{i}, r_{i} \leq 2$ với mọi $i$ $i$
Subtask $5$ $5$ $-$ $-$ $20$ $20$ điểm: Không có ràng buộc gì thêm

Notes

Trong ví dụ đầu tiên, các luật lệ được hiểu như sau:

Nếu vị trí $0$ $0$ có trồng hoa thì $3$ $3$ vị trí ngay bên phải $($ $($ vị trí $1,2,3$ $1, 2, 3$ $)$ $)$ không được trồng hoa.
Nếu vị trí $1$ $1$ có trồng hoa thì $1$ $1$ vị trí ngay bên trái $($ $($ vị trí $0$ $0$ $)$ $)$ không được trồng hoa.
Nếu vị trí $2$ $2$ có trồng hoa thì $1$ $1$ vị trí ngay bên phải $($ $($ vị trí $3$ $3$ $)$ $)$ không được trồng hoa.
Nếu vị trí $3$ $3$ có trồng hoa thì $2$ $2$ vị trí ngay bên trái $($ $($ vị trí $1,2$ $1, 2$ $)$ $)$ không được trồng hoa.
Nếu vị trí $4$ $4$ có trồng hoa thì $1$ $1$ vị trí ngay bên trái $($ $($ vị trí $3$ $3$ $)$ $)$ không được trồng hoa.

Minh họa của việc cắt bỏ các bông hoa như sau:

Trồng hoa

Input

Output

Examples

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Scoring

Notes

Comments