### PROBLEM LINK:

**Author:** Pawel Kacprzak

**Tester:** Misha Chorniy

**Editorialist:** Pawel Kacprzak

### DIFFICULTY:

SIMPLE

### PREREQUISITES:

Sorting, sweep line

### PROBLEM:

For a list of N positive consecutive heights: h_1, h_2, \ldots, h_N denoting some heights at which a plane was during its flight and knowing that between heights h_i and h_{i+1} it was flying the shortest path between these height, which means it was at every height between these two ones once, find the maximum integer K, such that the plane was K times at some height during the flight.

### QUICK EXPLANATION:

For every pair of consecutive heights h_i, h_{i+1} add each of these heights as either opening or closing time event to a list of all events, let’s call it E, happening in time. Sort E and process it using sweep line keeping track of the number of current opened events that has not been closed. The result is the maximum number of opened events during this process.

### EXPLANATION:

### Subtask 1

In this subtask N is at most 1000 and we know that each h_i \leq 1000. This allows the following approach:

Let K be the result to the problem and H be the set of some candidate heights such that the plane was at some h \in H exactly K times. If H is not too big, then we can for each h \in H check how many times the plane was at height h by iterating over all two consecutive input heights h_i, h_{i+1} and counting the number of such pairs that contain h. The answer to the problem is the maximal such count. This approach has the time complexity of O(|H| \cdot N), but how to chose H? Well, we can take advantage of the fact that h_i \leq 1000. Important thing to notice is that the height on which the plane was the most number of times can be a real number, not integer. However, the crucial observation is that we can put to H all positive integers not greater than 1000 and also floating points exactly between them, so 1.5, 2.5, \ldots. Is turns out that these candidate heights are sufficient because all input heights are integers.

### Subtask 2

In the second subtask N can be at most 10^5 and each h_i \leq 10^9, so method described above will take too much time. The crucial observation to approach the problem is to notice that if K is the answer to the problem, there exists height h for which there exists i such that \min(h_i, h_{i+1}) \le h \le \max(h_i, h_{i+1}) and the plane was at height h exactly K times. Thus the problem can be reduced to finding a point which is covered by most of these height pairs and returning the maximum size of such cover. Let’s think of pairs of consecutive heights as segments from the smaller to the larger height. Notice that changing height from h_i to h_{i+1} corresponds to one such segment. Moreover, the reduced problem can be easily solved using a sweep line algorithm by sorting all endpoints of the segments, then processing them from left to right counting the number of opened segments and returning the maximal such count during this process. The complexity of this solution is O(N \cdot \log(N)) dominated by the sorting phase.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution can be found here.

Tester’s solution can be found here.