Maximal Non-Overlapping Tasks

You are given a list of tasks, each represented by a pair of integers (start_time, end_time). Your task is to determine, for each starting index k (where k ranges from 1 to N), the maximum number of non-overlapping tasks that can be completed when considering only the tasks from k to N in the given order.

More formally, for each k such that 1 ≤ k ≤ N, select a subset of tasks from tasks[k-1], tasks[k], ..., tasks[N-1] so that no two tasks overlap (i.e. if you choose a task (s,t) then you cannot choose another task (s',t') with s' < t). You should follow a greedy strategy: iterate over the tasks from the k-th task to the last task, selecting a task if its start time is greater than or equal to the end time of the last selected task.

The answer is a list of N integers where the i-th integer is the maximum number of non-overlapping tasks that can be completed if you start from the i-th task.

Note: The tasks are processed in the order they are given and are not sorted. The algorithm should work with the input order directly.

The mathematical formulation can be expressed as follows:

$$\text{result}[i] = \max \{ \# \text{ of tasks selected from tasks } i \text{ to } N \}\ \text{where if } (s_j,t_j) \text{ and } (s_k,t_k) \text{ are two chosen tasks with } j < k, \text{ then } s_k \ge t_j. $$

inputFormat

The first line contains an integer N, the number of tasks. The following N lines each contain two space-separated integers, representing the start time and end time of a task.

Example:

5
1 3
2 5
4 6
7 9
8 10

outputFormat

Output N lines. Each line contains one integer: the maximum number of non-overlapping tasks that can be completed when starting at that task.

Example:

3
2
2
1
1

## sample

5
1 3
2 5
4 6
7 9
8 10

3
2
2
1
1

</p>