Set

Limits: 4 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Schoolboy, do you know what a set is? A set of numbers is a collection of numbers that do not repeat.

There is a set \(S\), which is initially empty. You need to process \(q\) such queries.

• \(l\ r\) — add all integers from \(l\) to \(r\) inclusive to \(S\). After executing each query, output the size of the set \(S\).

Input

The first line contains an integer \(q\) — the number of queries.

The next \(q\) lines each contain two integers \(l\), \(r\) — the parameters of the queries.

Output

For each of the \(q\) queries, output a single line — the size of the set \(S\) after the query.

Constraints

\(1 \le q \le 4 \cdot 10^5\),

\(1 \le l_i \le r_i \le 10^9\).

The scoring consists of the following subtasks:

• 1 point for each example from the problem statement,

• 20 points: \(r_{i - 1} < l_i\),

• 17 points: \(q \le 1000\), \(l_i \le r_i \le 1000\),

• 30 points: \(l_i \le r_i \le 10^6\),

• 31 points: no additional constraints.

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

In the first example, the set will change as follows: \(\{\} \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 \}\).