This problem, like its simpler bronze variant, requires a bit of thought beforehand in terms of characterizing the structure of a solution.

For the minimum, we generally want to look for the length-$N$ window of the number line containing the most cows (i.e., the fewest empty spaces), since with care, we can ensure that in any such window, we can fill in the $x$ empty spaces in the window by exactly $x$ moves. The only exception, which we handle as a special case, is a set of $N-1$ consecutive cows, then a gap of size more than 2, then another cow -- this case requires 2 moves instead of just 1. To find an optimal window, we sort the cows and slide two indices ($i$ and $j$ in my code below) representing the start and end of the window through this ordering, moving the end index in response to the start index.

For the maximum, the insight is similar to that in the bronze version of this problem. Suppose the cows are located at $A[0] \ldots A[N-1]$ in sorted order, and consider the two endpoint gaps of sizes $A[1]-A[0]$ and $A[N-1]-A[N-2]$. Our first move must "sacrifice" one of these gaps --- meaning that we can't move any cows into the gap. Aside from this one gap, however, we can ensure that a cow lands on every single empty space in our lineup between $A[0]$ and $A[N-1]$. We can do this by toggling between a state where there are two adjacent cows on the left of the ordering and a state where there are two adjacent cows on the right side of the ordering. In my code below, I could have written the answer as the number of empty spaces mines the smaller of the two gaps above, but instead I've equivalently written it as the number of spaces left over when the gaps are removed from consideration.

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
 
int N, A[100000];
 
int solve_min(void)
{
  if (A[N-2]-A[0] == N-2 && A[N-1]-A[N-2]>2) return 2;
  if (A[N-1]-A[1] == N-2 && A[1]-A[0]>2) return 2;
  int i, j=0, best=0;
  for (i=0; i<N; i++) {
    while (j<N-1 && A[j+1]-A[i]<=N-1) j++;
    best = max(best, j-i+1);
  }
  return N-best;
}
 
int main(void)
{
  ifstream fin ("herding.in");
  fin >> N; 
  for (int i=0; i<N; i++) fin >> A[i];
  sort (A, A+N);
 
  ofstream fout ("herding.out");
  int answer_min = solve_min();
  int answer_max = max(A[N-2]-A[0], A[N-1]-A[1]) - (N-2);
  fout << answer_min << "\n" << answer_max << "\n";
  return 0;
}