BubblePosters

Many artists announced their concerts for the upcoming holidays. Currently, there is an advertising war going on. Several agencies engaged workers to put posters on the street. In Bubble City there is only one (although very long) wall along the main street where posters are allowed. In the advertising union they have an agreement not to put posters over other, recently put posters. To make that agreement hold, they introduced a rule that an agency can send workers only if they are given a specific section of the wall which to cover fully with the posters. The section is specified by start and end positions.

Since there is little time left to the beginning of the show, agencies started to play rough: they still obey the rule about specifying sections in advance, but they do not care anymore about what was on the wall before. There are n sections specified and each of them is covered by a different poster. Workers come out one after the other.

After the concerts, agencies will want to analyze the effects of the campaign and they have to know for each different poster, on how much of the wall is their poster still visible? They will certainly employ some programmers. Are you interested?