A. A Non-Palindromic Modification
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

A sequence $$$a$$$ of length $$$n$$$ is called palindromic if $$$a_i=a_{n-i+1}$$$ for all $$$1 \leq i \leq n$$$.

You are given the sequence $$$b$$$ of $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$. Determine whether it is possible to increase exactly one element of $$$b$$$ by $$$1$$$ in such a way that the resulting sequence will not be palindromic.

Input

The first line of the input contains one integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the length of the input sequence. The $$$i$$$-th of the following $$$n$$$ lines contains one integer $$$b_i$$$ ($$$1 \leq b_i \leq 1000$$$) — the $$$i$$$-th element of sequence $$$b$$$.

Output

If it is possible to increase exactly one $$$b_i$$$ by $$$1$$$ and get the sequence that is not palindromic, print 1 in the only line of the output. Otherwise, print 0.

Examples
Input
1
1
Output
0
Input
2
20
21
Output
1