Множина

Limits: 4 sec., 512 MiB

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

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

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

Input

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

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

Output

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

Constraints

\(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 бал: без додаткових обмежень.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 1 4 7 10 2 3 6 12	4 8 8 11

Input (stdin) сopy	Output (stdout) сopy
7 2 3 7 11 44 47 1 10 23 34 777 796 4 7	2 7 11 15 27 47 47

Notes

У першому прикладі множина змінюватиметься так: \(\{\} \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 \}\).