Lấp chỗ trống

Cho một mảng $a$ gồm $n$ số nguyên không âm, nhưng một số phần tử đã bị mất và được đánh dấu bằng giá trị $-1$. Đảm bảo có ít nhất một phần tử bị mất.

Bạn cần chọn một số nguyên $k$ với $0\le k\le {10}^9$ rồi thay tất cả các phần tử bị mất trong mảng bằng $k$.

Gọi $m$ là hiệu tuyệt đối lớn nhất giữa hai phần tử kề nhau sau khi thay, tức là

$$m={max}_{1\le i\le n-1}|a_i-a_{i+1}|.$$

Hãy chọn $k$ sao cho $m$ nhỏ nhất có thể.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ — số lượng bộ test.
• Với mỗi bộ test:
  • Dòng đầu chứa số nguyên $n$ — kích thước mảng.
  • Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$. Nếu $a_i=-1$ thì phần tử thứ $i$ bị mất.

Dữ liệu ra

Với mỗi bộ test, in ra trên một dòng hai số nguyên: giá trị $m$ nhỏ nhất có thể và một số nguyên $k$ ($0\le k\le {10}^9$) đạt được giá trị $m$ đó. Nếu có nhiều $k$ hợp lệ, in ra bất kỳ giá trị nào.

Ràng buộc

• $1\le t\le {10}^4$
• $2\le n\le {10}^5$
• $-1\le a_i\le {10}^9$
• Mỗi bộ test có ít nhất một phần tử bị mất.
• Tổng của $n$ trên tất cả các bộ test không vượt quá $4·{10}^5$.

Ví dụ