Choose_Interval — RMI contest
Task type: batch | Time limit: 1.5 s | Memory limit: 256 MB | Difficulty: 24
Algorithms: heap, greedy, binary search

## Problem Choose Interval

Input file: `stdin`
Output file: `stdout`

You are given an infinite array of zeros with positions indexed by the integers and $N$ intervals of positions of the form $[A, B]$. For every given interval, you have to use one of the following two operations to execute on the array:

**Normal:** Add 1 to all positions in the array from $A$ to $B$.
**Flipped:** Add 1 to all positions in the array *except* those from $A$ to $B$.

You want to choose a type of operation to execute for each interval so that the maximum value stored in the array after applying all operations is minimized.

## Input data

The first line of the input contains the number of intervals $N$. The next $N$ lines each contain two space-separated integers, $A$ and $B$, representing the endpoints of an interval.

## Output data

The first line of the output should contain the maximum value in the array after executing the $N$ operations optimally.

The second line should contain a binary string of length $N$, with the $i$-th character being 0 if the $i$-th used operation was flipped and 1 if it was normal.

If there are multiple ways of choosing the operations optimally, any valid solution is accepted.

## Restrictions

*   $1 \le N \le 200\,000$
*   $1 \le A \le B \le 2N$

| #   | Points | Restrictions             |
| --- | ------ | -------------------------- |
| 1   | 7      | $N \le 20$               |
| 2   | 24     | $N \le 150$              |
| 3   | 21     | $N \le 1\,000$             |
| 4   | 34     | $N \le 50\,000$            |
| 5   | 14     | No further restrictions. |

## Examples

| Input file | Output file | Explanations               |
| :--------- | :---------- | :------------------------- |
| 5          | 2           | Another valid answer would be: |
| 10 10      | 11110       | 2                          |
| 6 6        |             | 11011                      |
| 1 7        |             |                            |
| 2 5        |             |                            |
| 2 7        |             |                            |

Starter code: