Problem J
Paludarium

Source: Photo by Sventie

Feeling lonely in his apartment since he is quarantined inside at the moment, Bob decided to make use of the fish tank left by the previous renter to set up a little paludarium (a semi-aquatic habitat that combines land and water environments) and fill it with little creatures to keep him company at home.

As he is testing out different layouts, Bob wonders if his landscape would provide a good ratio of water and air space for his new pets. To simplify this problem, Bob imagines the tank to be a 2D grid which will be filled with solid land blocks of different heights from his current landscape construction. To achieve the optimal balance, his goal is to figure out what is the minimum difference he can achieve between the number of square blocks occupied with water versus the number of square blocks that are occupied with air in his tank. As Bob fills water into the tank, the water will rise evenly across an entire block layer at a time, so any blocks of air at that level will be replaced with blocks of water. Each square is either water, air, or land (fractional squares are not possible in Bob’s design).

Given a list of integers representing the different land block heights present in the tank from left to right, output the water level necessary to minimize the difference between water and air to achieve optimal balance. If there are multiple water levels that can achieve the optimal balance, output the smallest such level. Also compute the amount of water that will be needed.

For example, suppose the layout of the tank can be represented by a list of integers $[0, 0, 2, 0, 1]$ where each integer is the height of land blocks at a column in the tank, counted from left to right, with a tank’s overall height of $3$ and width of $5$ (as shown by the illustration below which corresponds to Sample Input 1).

Figure 1: Tank layout

As shown in Figure 2, filling up to a height of $1$ with water results in $3$ water blocks and $9$ air blocks (a difference of $6$).

Figure 2: Tank layout with water level of 1

As shown in Figure 3, filling up to a height of $2$ with water results in $7$ water blocks and $5$ air blocks (for a difference of $2$), which is the optimal difference that Bob wants for this input.

Figure 3: Tank layout with water level of 2

Input

The input consists of $2$ lines. The first line contains two integers $H$ and $W$ describing the height and width of the tank ($1 \le H \le 10^{9}$, $1 \le W \le 5 \cdot 10^{5}$). The second line contains $W$ integers $B_ i$ where each $B_ i$ is the height of the land blocks at the $i^{\text {th}}$ column of the tank, counted from left to right ($0 \le B_ i \le H$ for $i = 1 \ldots W$).

Output

Print two integers, the first one describing the smallest water level that achieves the optimal balance and the second one providing the total number of water blocks in Bob’s tank at this level. If adding no water yields the optimal balance, output 0 0.

3 5
0 0 2 0 1

2 7

6 6
4 0 3 5 2 1

4 10