You are given \(n\) boxes and each box contains two small boxes of Red and Blue color. The size of the Red and Blue colored boxes are \(b_i\) and \(r_i\) respectively.
Consider a sequence of distinct integers \(x_1, x_2, \ldots, x_k\ (1 \le x_i \le n)\).
Consider \(x\) to be a suitable sequence if, for every \(1 \le i < k\ holds\ b_{x_i} < r_{x_{i+1}}\ and\ r_{x_i} < b_{x_{i+1}}\).
Determine the maximum possible size of the suitable sequence.
Input format
- First line: \(n\) representing the number of available boxes \((1 \leq n \leq 5 \cdot 10^5)\)
- Next \(n\) lines: Two positive integers \(r_i\) and \(b_i\) \((1\leq r_i,\ b_i \leq 10^9)\)
Output format
Print only one integer representing the size of the maximum suitable sequence.
3 1 2 2 3 3 4
2
sequence $$[1,3]$$ is suitable since $$b_1 < r_3$$ and $$r_1 < b_3$$. Its size is 2 and it can be shown that we can't arrange all 3 girls to form a suitable sequence of size \(3\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor