YES

TRS:

  min(x,0()) -> 0()
  min(0(),y) -> 0()
  min(s(x),s(y)) -> s(min(x,y))
  max(x,0()) -> x
  max(0(),y) -> y
  max(s(x),s(y)) -> s(max(x,y))
  -(x,0()) -> x
  -(s(x),s(y)) -> -(x,y)
  gcd(s(x),0()) -> s(x)
  gcd(0(),s(x)) -> s(x)
  gcd(s(x),s(y)) -> gcd(-(max(x,y),min(x,y)),s(min(x,y)))

max/plus interpretations on N:

  min_A(x1,x2) = max{12, 10 + x1, -35}
  min#_A(x1,x2) = max{31, -1 + x1, 30}
  0_A = 12
  0#_A = 0
  s_A(x1) = max{48, 34 + x1}
  s#_A(x1) = max{46, 22 + x1}
  max_A(x1,x2) = max{2, 1 + x1, 18 + x2}
  max#_A(x1,x2) = max{22, -9 + x1, 6 + x2}
  -_A(x1,x2) = max{18, x1, -9 + x2}
  -#_A(x1,x2) = max{74, 73, 72}
  gcd_A(x1,x2) = max{11, 11 + x1, x2}
  gcd#_A(x1,x2) = max{58, 26 + x1, 11 + x2}

precedence:

  max > s > gcd > min = - > 0