Ще більше справ

Обмеження: 2 сек., 256 МіБ

Як вам уже відомо, у Зеника дуже багато справ. Усього в нього є \(n\) справ, \(i\)-а з них триватиме від моменту часу \(l_i\) до \(r_i\). Зауважте, що справи можуть довільним чином накладатися чи перетинатись.

Цього разу Зеник вирішив, що він може деякі зі справ перенести на завтра. Зеник дуже не любить, коли справи перетинаються, тому він хоче якнайбільше розбити такі справи між різними днями.

Нехай \(f(a, b)\) — це довжина перетину справ \(a\) й \(b\). Наприклад, \(f([2, 7], [4, 10])=3\), \(f([4, 7], [2, 10])=3\), \(f([2, 4] , [7, 10])=0\).

Нехай множина справ, які Зеник виконає сьогодні — \(A\), завтра — \(B\).

Тоді Зеник хоче максимізувати \[c=\sum_{a \in A} \sum_{b \in B} {f(a,b)}.\]

Допоможіть йому із цим.

Вхідні дані

У першому рядку задано ціле число \(n\) — кількість справ.

У наступних \(n\) рядках задано по два цілих числа \(l_i\) та \(r_i\) — межі проміжку \(i\)-ої справи.

Вихідні дані

У першому рядку виведіть максимальне значення \(c\).

У другому рядку виведіть \(n\) чисел 0 або 1. 1 означає, що Зеник виконає відповідну справу сьогодні, 0 — завтра.

Обмеження

\(1 \le n \le 10^5\),

\(0 \le l_i < r_i \le 10^9\).

Приклади