Mảng Kalindrome (Kalindrome Array)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một mảng $[b_1,b_2,\ldots,b_m]$ được gọi là đối xứng nếu:

$$b_i=b_{m+1-i}$$

với mọi $1\le i\le m$.

Mảng rỗng cũng được xem là một mảng đối xứng.

Một mảng được gọi là kalindrome nếu tồn tại một số nguyên $x$ sao cho ta có thể xóa một số phần tử có giá trị bằng $x$, và sau khi ghép các phần còn lại lại với nhau, mảng thu được là một mảng đối xứng.

Lưu ý:

• Chỉ được chọn một giá trị $x$ duy nhất.
• Sau khi chọn $x$, chỉ những phần tử có giá trị bằng $x$ mới được phép xóa.
• Không bắt buộc phải xóa tất cả các phần tử bằng $x$.
• Cũng không bắt buộc phải xóa phần tử nào. Vì vậy, mọi mảng vốn đã đối xứng đều là kalindrome.

Ví dụ:

• $[1,2,1]$ là kalindrome vì bản thân mảng đã đối xứng, nên không cần xóa phần tử nào.
• $[3,1,2,3,1]$ là kalindrome. Có thể chọn $x=3$ và xóa hai phần tử bằng $3$, thu được $[1,2,1]$, là một mảng đối xứng.
• $[1,2,3]$ không phải là kalindrome.

Cho mảng:

$$a=[a_1,a_2,\ldots,a_n].$$

Hãy xác định xem $a$ có phải là một mảng kalindrome hay không.

Input

Dòng đầu tiên chứa số nguyên $n$ — số phần tử của mảng.

Dòng thứ hai chứa $n$ số nguyên:

$$a_1,a_2,\ldots,a_n.$$

Output

In ra:

• YES nếu mảng $a$ là kalindrome;
• NO nếu mảng $a$ không phải là kalindrome.

Có thể in các chữ cái dưới dạng chữ hoa hoặc chữ thường.

Subtask

• Subtask 1 — 30% — Time Limit: 1.00 s: $1\le n\le 2000$; $1\le a_i\le n$.
• Subtask 2 — 70% — Time Limit: 1.00 s: $1\le n\le 2\cdot10^5$; $1\le a_i\le n$.

Ví dụ

Ví dụ 1

Input

1
1

Output

YES

Giải thích

Mảng ban đầu là:

$$[1].$$

Mảng chỉ có một phần tử nên đã đối xứng.

Ta không cần xóa bất kỳ phần tử nào. Vì vậy mảng là kalindrome và kết quả là YES.

Ví dụ 2

Input

2
1 2

Output

YES

Giải thích

Mảng ban đầu là:

$$[1,2].$$

Chọn:

$$x=2.$$

Xóa phần tử có giá trị $2$, ta thu được:

$$[1].$$

Mảng $[1]$ là đối xứng.

Do đó mảng ban đầu là kalindrome và kết quả là YES.

Ví dụ 3

Input

3
1 2 3

Output

NO

Giải thích

Mảng ban đầu là:

$$[1,2,3].$$

Mảng này không đối xứng.

Nếu chọn $x=1$ và xóa phần tử $1$, ta thu được:

$$[2,3],$$

không đối xứng.

Nếu chọn $x=2$ và xóa phần tử $2$, ta thu được:

$$[1,3],$$

không đối xứng.

Nếu chọn $x=3$ và xóa phần tử $3$, ta thu được:

$$[1,2],$$

cũng không đối xứng.

Việc không xóa phần tử nào cũng không tạo được mảng đối xứng.

Vì chỉ được chọn một giá trị $x$, không tồn tại cách xóa hợp lệ nào để biến mảng thành đối xứng.

Do đó kết quả là NO.

Ví dụ 4

Input

5
1 4 4 1 4

Output

YES

Giải thích

Mảng ban đầu là:

$$[1,4,4,1,4].$$

Có thể chọn:

$$x=4$$

và chỉ xóa phần tử $4$ cuối cùng.

Mảng còn lại là:

$$[1,4,4,1].$$

Ta có phần tử thứ nhất bằng phần tử thứ tư và phần tử thứ hai bằng phần tử thứ ba, nên đây là một mảng đối xứng.

Vì vậy mảng ban đầu là kalindrome và kết quả là YES.

Một cách khác cũng hợp lệ là chọn $x=1$, xóa hai phần tử bằng $1$ để thu được:

$$[4,4,4],$$

cũng là một mảng đối xứng.