Problem H
Hiring and Firing
Unfortunately, due to labor laws, the firing of workers must follow a last-in-first-out order: the people who have been employed the shortest time must be fired first. Furthermore, a fired person cannot be re-hired within the foreseeable future so it is not possible to circumvent the law by firing some people and then immediately re-hiring some of them.
But this story is actually about HR, not workers! Every day, one employee from the HR department is assigned to be responsible for giving the fired workers the bad news that they are fired, and for then giving the newly hired workers the good news that they are hired. In order to minimize work environment problems in the form of social awkwardness for the HR staff, a policy has been established requiring that the HR person firing an employee must always be a different HR person than the one welcoming them when they were hired.
Now the time has come for the HR department to also optimize itself, by making itself as small as possible. Unlike workers, new HR staff cannot be hired with short notice, so the HR personnel must be permanent employees. What is the smallest number of HR people needed in order to manage all the planned hirings and firings?
Input
The first line of input contains an integer $n$ ($1 \le n \le 10^5$), the length in days of the foreseeable future. Then follow $n$ lines, the $i$th of which contains two integers $f_ i$ and $h_ i$ ($0 \le f_ i, h_ i \le 10^6$) where $f_ i$ is the number of workers fired on day $i$ and $h_ i$ the number of people hired.
The number of workers fired on a day is never larger than the number of currently employed workers (in other words, $f_ i \le \sum _{j=0}^{i-1} h_ j-f_ j$ for all $1 \le i \le n$).
Output
Output a line with an integer $k$, the smallest number of HR people needed. The HR people are arbitrarily given IDs from $1$ to $k$. Then output a line with $n$ integers, the $i$th of which contains the ID of the HR person in charge of the firing and hiring on day $i$. If there is more than one solution, any one will be accepted.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 0 3 1 1 2 1 2 0 |
3 1 2 3 2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 0 10 0 5 2 0 0 0 0 100 50 100 |
2 1 2 1 2 1 2 |
