Множина

Обмеження: 4 сек., 512 МіБ

Школяре, ти знаєш, що таке множина? Множина чисел — це набір чисел, які не повторюються.

Є множина $S$, яка спочатку порожня. Тобі потрібно опрацьовувати такі $q$ запитів.

• $l\ r$ — до $S$ потрібно додати всі цілі числа від $l$ до $r$ включно. Після виконання кожного запиту виведи розмір множини $S$.

Вхідні дані

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

У наступних $q$ рядках задано по два цілі числа $l$, $r$ — параметри запитів.

Вихідні дані

Для кожного з $q$ запитів виведи один рядок — розмір множини $S$ після запиту.

Обмеження

$1 \le q \le 4 \cdot 10^5$,

$1 \le l_i \le r_i \le 10^9$.

Оцінювання складається з таких блоків:

• по 1 балу за кожен приклад з умови,

• 20 балів: $r_{i - 1} < l_i$,

• 17 балів: $q \le 1000$, $l_i \le r_i \le 1000$,

• 30 балів: $l_i \le r_i \le 10^6$,

• 31 бал: без додаткових обмежень.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 1 4 7 10 2 3 6 12	4 8 8 11

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 2 3 7 11 44 47 1 10 23 34 777 796 4 7	2 7 11 15 27 47 47

Примітки

У першому прикладі множина змінюватиметься так: $\{\} \rightarrow \{ 1, 2, 3, 4 \} \rightarrow \{ 1, 2, 3, 4, 7, 8, 9, 10 \} \rightarrow \{ 1, 2, 3, 4, 7, 8, 9, 10 \} \rightarrow \{ 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12 \}$.