Dãy số tăng

Bối cảnh

Cho dãy số nguyên dương gồm \(n\) phần tử \(a_1, a_2,..., a_n\). Bạn có thể sử dụng bao nhiêu thao tác tùy ý (có thể không dùng) để thay đổi các phần tử của dãy.

Yêu cầu

Với một thao tác bạn được chọn hai số \([l, r]\) bất kì sao cho \(1\leq l < r\leq n\), và đảo ngược vị trí của các phần tử trong đoạn từ \(l\) đến \(r\) đó. Nói cách khác, bạn có thể biến đổi dãy con \([a_l, a_{l+1},..., a_r]\) thành \([a_r, a_{r-1},... a_l]\) trong một thao tác.

Ví dụ: Cho \(n = 5\) và dãy \([1, 4, 2, 3, 5]\), chọn \(l = 2\) và \(r = 4\), sau khi biến đổi dãy sẽ được đổi thành \([1, 3, 2, 4, 5]\).

Nhiệm vụ của bạn là kiểm tra xem dãy số đã cho có thể biến đổi thành dãy tăng sau một vài thao tác không.

Input

Dòng đầu tiên chứa một số nguyên \(t\ (1\leq t\leq 10^4)\) - số lượng test.

Dòng đầu tiên của mỗi test chứa một số nguyên \(n\ (1\leq n\leq 20)\) - độ dài của dãy.

Dòng thứ hai của mỗi test chứa \(n\) số nguyên \(a_1, a_2,... a_n\ (1\leq a_i\leq 10^9)\) - các phần tử của dãy.

Output

In ra \(t\) dòng, mỗi dòng là kết quả của mỗi testcase. Nếu dãy đã cho thỏa mãn in ra YES, ngược lại in ra NO.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

2
5
1 4 2 3 5
6
10 9 8 8 2 1

Output

YES
NO

Giải thích ví dụ

• Ví dụ 1:

  • Dữ liệu: n = 5, dãy [1, 4, 2, 3, 5]
  • Giải thích: Bạn có thể chọn đoạn từ vị trí 2 đến 4 và đảo ngược nó để biến dãy thành [1, 3, 2, 4, 5], dãy này đã được sắp xếp tăng dần.

• Ví dụ 2:

  • Dữ liệu: n = 6, dãy [10, 9, 8, 8, 2, 1]
  • Giải thích: Dù bạn có thực hiện các thao tác đảo ngược, không thể sắp xếp dãy này thành dãy tăng dần.

Bạn cần kiểm tra xem dãy có thể trở thành dãy tăng dần sau một số thao tác đảo ngược không.

Thông tin học tập

• Buổi: B16
• Concepts: sorting, duplicate detection, arrays/vectors
• Giới hạn kiến thức: B01-B16
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 15