Множина

Обмеження: 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 \}\).