Jagged Skyline

문제

The future is here! The Boxes And Parcels Centre has decided to start delivering parcels using drones. Being a BrAinPort Company, naturally the first deliveries will be to Eindhoven.

To keep the flight logic simple, the first prototype will only deliver to the roofs of the tallest buildings. After take-off, the drone will take a $w\times hw\backslash times\; h$ ($1\le w\le 100001\; \backslash leq\; w\backslash leq\; 10\backslash ,000$, $1\le h\le {10}^{18}1\backslash leq\; h\backslash leq\; 10^\{18\}$) photo of the skyline, as shown in Figure J.1. You have been tasked with the problem of determining the location and height of the tallest building in this photo, so that the drone knows where to go.

You have access to a classifier that can determine for each pixel whether it is "sky" or "building". You can use this multiple times for different pixels. To avoid unnecessary delays, you may run the classifier at most $1200012\backslash ,000$ times.

It is guaranteed that the buildings will not contain any hovering parts: whenever a pixel that is not on the bottom row of the photo is classified as building, the pixels below it will also be classified as building.

Figure J.1: The skyline of the sample interaction.