Lây lan Virus Zombie

Bối cảnh

Có N người trên phố (được đánh số từ 1 đến N). Đơn giản hơn, chúng ta sẽ coi họ như những điểm trên một đoạn thẳng. Với mỗi i, vị trí của người thứ i là \( X_i \).

Yêu cầu

Có chính xác một trong số những người này đã bị lây nhiễm virus zombie, nhưng chúng ta không biết đó là ai. Virus zombie sẽ lây lan từ người bị nhiễm sang người không nhiễm bệnh bất cứ khi nào khoảng cách giữa họ tối đa là 2. Nếu chúng ta chờ đủ lâu, một nhóm người cụ thể (tùy thuộc vào người bị nhiễm ban đầu) sẽ bị lây nhiễm; kích thước của tập hợp này được gọi là số người nhiễm zombie cuối cùng.

Nhiệm vụ của bạn là tìm ra giá trị nhỏ nhất và lớn nhất của số người bị nhiễm zombie cuối cùng, tức là tìm ra con số này trong trường hợp tốt nhất và trong trường hợp xấu nhất có thể xảy ra.

Input

• Dòng đầu tiên chứa một số nguyên \( T \) – số lượng test.
• \( T \) test được mô tả như sau:
  • Dòng đầu tiên của mỗi test chứa một số nguyên \( N \).
  • Dòng thứ hai chứa \( N \) số nguyên \( X_1, X_2, \ldots, X_N \).

Output

• Với mỗi test, in ra một dòng chứa hai số nguyên – giá trị nhỏ nhất và lớn nhất của số người bị nhiễm zombie cuối cùng.

Ràng buộc

• \( 1 \leq T \leq 2,000 \)
• \( 2 \leq N \leq 8 \)
• \( 0 \leq X_i \leq 10 \) với mọi \( i \)
• \( X_1 < X_2 < \ldots < X_N \)

Ví dụ 1

Input

3
2
3 6
3
1 3 5
5
1 2 5 6 7

Output

1 1
3 3
2 3

Giải thích ví dụ

• Ví dụ 1: Khoảng cách giữa hai người là 3, do đó virus zombie không thể lây lan và đến cuối cùng, sẽ vẫn chỉ có một người duy nhất bị nhiễm bệnh.
• Ví dụ 2: Khoảng cách giữa hai người liền kề bất kỳ là 2, vì vậy đến cuối cùng tất cả họ đều bị nhiễm zombie.
• Ví dụ 3:
  • Ở một trong số những khả năng tốt nhất, người ở vị trí 1 là người mang virus zombie ban đầu và virus cũng sẽ lây lan đến người ở vị trí 2.
  • Ở một trong các tình huống xấu nhất, người ở vị trí thứ 5 mang virus zombie ban đầu và virus sẽ lan đến người ở vị trí 6 và 7.

Thông tin học tập

• Buổi: B09
• Concepts: 1D arrays, consecutive groups
• Giới hạn kiến thức: B01-B09
• Time limit: 2 seconds
• Memory limit: 64 MB
• Point: 20