Hoán vị và Phép đổi chỗ

Trong một buổi thảo luận trực tuyến về thuật toán, FullHouse Dev đã gặp một bài toán thú vị liên quan đến hoán vị và phép đổi chỗ. Với sự hỗ trợ của internet và kiến thức sẵn có, họ bắt đầu phân tích và giải quyết vấn đề này.

Bài toán

FullHouse Dev được cung cấp một mảng \(A\) có \(n\) phần tử nguyên. Họ có thể thực hiện phép toán sau đây trên mảng \(A\) bao nhiêu lần tùy ý:

Chọn hai chỉ số \(i\) và \(j\) sao cho \(i < j\), sau đó giảm \(A[i]\) đi \(1\) và tăng \(A[j]\) lên \(1\).

Nhiệm vụ của nhóm là xác định xem có thể biến đổi mảng \(A\) thành một hoán vị của các số từ \(1\) đến \(n\) hay không.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng bộ test.
• Với mỗi bộ test:
  • Dòng đầu tiên chứa một số nguyên \(n\) - độ dài của mảng \(A\).
  • Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, ..., A_n\) - các phần tử của mảng \(A\).

OUTPUT FORMAT:

• Với mỗi bộ test, in ra "YES" nếu có thể biến đổi mảng \(A\) thành một hoán vị, ngược lại in ra "NO".

Ràng buộc:

• \(1 \leq T \leq 10^5\)
• \(1 \leq n \leq 10^5\)
• \(1 \leq A_i \leq 10^9\)
• Tổng của \(n\) trong tất cả các bộ test không vượt quá \(10^6\)

Ví dụ

INPUT

2
4
3 3 2 2
3
2 1 2

OUTPUT

YES
NO

Giải thích

• Ở bộ test đầu tiên, FullHouse Dev có thể áp dụng phép toán trên các chỉ số \(1\) và \(4\), biến mảng thành \([2, 3, 2, 3]\), sau đó áp dụng trên các chỉ số \(2\) và \(3\), thu được \([2, 2, 3, 3]\), là một hoán vị của các số từ 1 đến 4.
• Ở bộ test thứ hai, không thể biến đổi mảng thành một hoán vị của các số từ 1 đến 3.

FullHouse Dev nhận ra rằng bài toán này không chỉ đòi hỏi kiến thức về thuật toán mà còn cần sự sáng tạo trong việc áp dụng các phép biến đổi. Họ quyết định chia sẻ bài toán này trên diễn đàn lập trình để thảo luận thêm với cộng đồng.