- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
A fly named McFly is going to a party tonight. Unfortunately for him, it’s a party for humans, not flies.
There is going to be a $10^9$ meter long table at the party, where humans put down their cookies for a while before they pick them up again later. That’s when McFly can buzz in and taste the cookie while the human is leaving his/her cookie unattended. Tasting cookies is McFly’s favorite thing to do. He doesn’t want to eat them, he just wants to enjoy tasting as many cookies as possible. He’ll enjoy tasting a cookie if it is different from the previous cookie he tasted, or if it is the first cookie he tastes at the party. That means he can enjoy tasting the same cookie multiple times, as long as he tastes at least one other cookie between every two tastings of the same cookie.
But McFly is prepared. He went to see a fortune-teller to know what is going to happen at the party. The fortune-teller told him about $n$ cookies, which are going to be put down on the table. The $i-th$ cookie is going to be at position $x_i$ (i.e. $x_i$ meters from start of the table), from time $s_i$ to $f_i$ (Times are measured in seconds, from the start of the party). It is guaranteed that no two cookies will be at the same position, at the same time; i.e., for every $i$ and $j$ where $i = j$ and $x_i = x_j$, either $f_i \leq s_j$ or $f_j \leq s_i$. More specifically, the table can be considered as a horizontal line on which McFly and the cookies are seen as points. McFly can be present at any position before the start of the party. At any time afterward, he can fly at the speed of $1$ meter per second along with the table, or stay in place. McFly can taste cookie $i$ if he is at position $x_i$ at some time $t$ where $s_i \leq t < f_i$. Tasting cookies take no time. Help McFly to enjoy as many tastes as possible.
ورودی
The first line of the input contains the integer $n$ ($1 \leq n \leq 100,000 $). The $i$-th line of the next $n$ lines contains three integers $x_i$, $s_i$, and $f_i$ ($0 \leq x_i \leq 10^9$, $0 \leq s_i < f_i \leq 10^9$). The total time of cookies being on the table is at most $10^5 \left( \sum_{i=1}^n f_i - s_i \leq 10^5 \right)$.
خروجی
Output the maximum number of new tastes McFly can enjoy.
ورودی نمونه ۱
4
7 2 5
1 2 4
4 1 6
2 9 10
خروجی نمونه ۱
3
ورودی نمونه ۲
3
0 0 11
2 0 11
3 4 9
خروجی نمونه ۲
8
ارسال پاسخ برای این سؤال