Integer Palindrome Array (Mảng đối xứng số nguyên)

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem

Given $a_0,a_1,\ldots,a_{n-1}$, the array is palindromic if

It is sufficient to check $0\le i<\lfloor n/2\rfloor$. Determine whether the array is palindromic.

Input

The first line contains $n$. The second line contains $n$ integers $a_i$.

Output

Print YES if the array is palindromic; otherwise print NO.

Subtask

Subtask 1 (20 points): $1\le n\le10$, $|a_i|\le10^3$.

Subtask 2 (30 points): $1\le n\le5000$, $|a_i|\le10^6$.

Subtask 3 (50 points): $1\le n\le2\cdot10^5$, $|a_i|\le10^9$.

Example

Input

7
1 4 -2 9 -2 4 1

Output

YES

Explanation

The sample follows the mathematical definition above.