Cho dãy \(A\) gồm \(N\) phần tử \(A_1, A_2, \dots, A_N\). Bạn được phép thay đổi vị trí các phần tử trong dãy \(A\) một cách tùy ý.
Hãy biến đổi dãy \(A\) sao cho sau khi biến đổi:

• Không tồn tại hai phần tử liên tiếp nào có cùng giá trị.

Với một dãy \(A\) bất kỳ, gọi

với mỗi cặp chỉ số \(i < j\) sao cho \(A_i = A_j\) và không tồn tại chỉ số \(k\) với \(i < k < j\) thỏa mãn \(A_i = A_k = A_j\).
Nói cách khác, với mỗi giá trị xuất hiện trong dãy, ta xét các vị trí xuất hiện của nó theo thứ tự tăng dần. Với mỗi hai lần xuất hiện liên tiếp của cùng một giá trị, ta tính hiệu chỉ số \(j - i\) và lấy giá trị lớn nhất trong tất cả các hiệu này. Nếu không tồn tại cặp chỉ số \(i, j\) thỏa mãn (tức là mọi phần tử đều phân biệt), khi đó \(D = 0\).

Yêu cầu: Hãy biến đổi dãy \(A\) (tức là chọn một hoán vị của các phần tử trong dãy ban đầu) sao cho:

• Không có hai phần tử liên tiếp bằng nhau;
• Giá trị \(D\) thu được là nhỏ nhất có thể.

Nếu không tồn tại cách biến đổi thỏa mãn điều kiện không có hai phần tử liên tiếp bằng nhau, hãy in ra \(-1\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(T\) là số bộ dữ liệu (\(1 \le T \le 100\)).
• Tiếp theo là \(T\) nhóm dòng, mỗi nhóm mô tả một bộ dữ liệu theo định dạng sau:
  • Dòng đầu tiên chứa một số nguyên dương \(N\) (\(1 \le N \le 5\cdot 10^5\)).
  • Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le N\)).

Dữ liệu đảm bảo tổng các giá trị \(N\) trong tất cả các bộ dữ liệu không vượt quá \(10^6\).

Output

Với mỗi bộ dữ liệu:

• Nếu không tìm được cách biến đổi thỏa mãn điều kiện không tồn tại hai phần tử liên tiếp nào có cùng giá trị, in ra một dòng duy nhất chứa số \(-1\).
• Ngược lại, in ra hai dòng:
  • Dòng thứ nhất chứa giá trị \(D\) nhỏ nhất tìm được.
  • Dòng thứ hai chứa \(N\) số nguyên dương là dãy \(A\) sau khi biến đổi (một hoán vị của dãy ban đầu) thỏa mãn các điều kiện đề bài.

Example

1
6
3 3 3 2 2 1

2
3 2 3 2 3 1

1
6
3 3 3 2 2 1

3
3 2 1 3 2 3

1
6
3 3 3 2 2 1

2
3 3 3 1 2 2

Scoring

Với mỗi bộ dữ liệu:

• Nếu cả thí sinh và ban giám khảo đều không tìm được cách biến đổi thỏa mãn, thí sinh được \(100\%\) số điểm cho bộ dữ liệu đó.
• Nếu cả thí sinh và ban giám khảo đều tìm được cách biến đổi thỏa mãn, gọi \(D_j\) là giá trị \(D\) trong lời giải của ban giám khảo, \(D_p\) là giá trị \(D\) trong lời giải của thí sinh.
  • Nếu \(D_p = D_j\):
    • Nếu thí sinh đưa ra được một cách biến đổi thỏa mãn (với đúng giá trị \(D_p\)), thí sinh được \(100\%\) số điểm.
    • Ngược lại, thí sinh được \(20\%\) số điểm.
  • Nếu \(D_p \neq D_j\):
    • Nếu thí sinh đưa ra được một cách biến đổi thỏa mãn (với đúng giá trị \(D_p\)), thí sinh được \(f(D_p, D_j) = (60 - \log_N ((D_p + 1)/(D_j + 1)) \cdot 60)\%\) số điểm.
    • Ngược lại, thí sinh được \(0\) điểm.
• Nếu ban giám khảo tìm được kết quả nhưng thí sinh không tìm được, thí sinh được \(0\) điểm cho bộ dữ liệu đó.

Điểm của thí sinh cho mỗi test là điểm nhỏ nhất mà thí sinh nhận được trên tất cả các bộ dữ liệu của test đó.

• Subtask 1 (\(4\) điểm): \(A_i \neq A_j\) với mọi \(i \neq j\) (\(1 \le i, j \le n\)).
• Subtask 2 (\(9\) điểm): \(N \le 10\).
• Subtask 3 (\(12\) điểm): \(A_i \le 2\), \(\forall i = 1..n\).
• Subtask 4 (\(17\) điểm): với mọi giá trị \(x\), số lần xuất hiện của \(x\) trong dãy \(A\) là như nhau.
• Subtask 5 (\(21\) điểm): \(A_i \le 3\), \(\forall i = 1..n\).
• Subtask 6 (\(17\) điểm): \(N \le 5000\).
• Subtask 7 (\(20\) điểm): Không có ràng buộc nào thêm.