Поликарп изобрел новую мобильную игру с падающими блоками.
В этой игре \(n\) блоков падают, по-одному за раз, на плоскую поверхность шириной \(d\) единиц. Каждый блок можно представить как прямоугольник с координатами от \(l_i\) до \(r_i\) и единичной шириной, падающий вниз с большой высоты. Блок падает, пока не столкнется с плоской поверхностью или другим блоком. Будем говорить, что блок \(a\) накрывает блок \(b\), если \(l_a \le l_b \le r_b \le r_a\).
Рассмотрим, что происходит, когда падает блок \(i\). Если этот (верхний) блок \(i\) сталкивается с любым блоком \(j\), таким что блок \(i\) не накрывает блок \(j\), то блок \(i\) упрется в блок \(j\), и все блоки останутся на месте. В противном случае, все блоки, с которыми блок \(i\) столкнулся и накрывает будут уничтожены, а блок \(i\) продолжит падать, не теряя способности уничтожать другие блоки.
Например, рассмотрим, что случится, когда будут падать блоки \((1,2)\), \((2,3)\) и \((1,3)\) в данном порядке. Первый блок приземлится на плоскую поверхность. Далее, второй блок упрется в первый блок. Наконец, третий блок сначала уничтожит второй блок, продолжит падать, уничтожит первый блок и приземлится на плоскую поверхность.
Выше изображен пример из условия, он же является первым примером. Помогите Поликарпу определить количество оставшихся блоков после падения каждого из них!
Примечание
Первый пример соответствует примеру из условия.
Во втором примере, происходят следующие изменения:
- Блок \(1\) приземлится на плоскую поверхность.
- Блок \(2\) приземлится на плоскую поверхность.
- Блок \(3\) приземлится на блоки \(1\) и \(2\). Заметим, что блок \(3\) не уничтожит блок \(2\), потому что не покрывает блок \(1\) и упирается в него.
- Блок \(4\) уничтожит все блоки и приземлится на плоскую поверхность.
- Блок \(5\) приземлится на блок \(4\).
- Блок \(6\) приземлится на блок \(5\).
- Блок \(7\) приземлится на блок \(6\). Заметим, что никакие блоки не будут уничтожены, потому что, хотя блок \(7\) покрывает блоки \(4\) и \(5\), но он их не касается.
- Блок \(8\) уничтожит блок \(7\) и приземлится на \(6\).