G. Nuôi mèo
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Chung có hai con mèo, mèo A và mèo B (nên nghĩ tên khác :>). Mỗi ngày trong $$$m$$$ ngày, Chung cho hai con mèo ăn cá. Trong ngày thứ $$$i$$$, Chung có $$$c_i$$$ con cá để chia cho hai con mèo ăn và hai con mèo phải ăn hết số cá này.

Tuy nhiên, hai con mèo này khá dị đặc biệt. Con mèo A ngày càng ăn nhiều, còn mèo B lại ngày càng ăn ít. Nghĩa là $$$\forall i \in [2,m], a_i \ge a_{i - 1}$$$ và $$$b_{i} \le b_{i - 1}$$$ với $$$a_i,b_i$$$ lần lượt là số con cá mà mèo A,B ăn trong ngày thứ $$$i$$$.

Chung muốn cho hai con mèo ăn sao cho số cá chênh lệch ($$$|a_i - b_i|$$$) tối đa trong $$$m$$$ ngày trên là nhỏ nhất. Hoặc cũng có thể không có cách cho hai con mèo ăn thỏa mãn các điều kiện trên. Khi đó, hãy in ra $$$-1$$$. Hãy giúp Chung nhé.

Input

Dòng đầu tiên chứa số nguyên dương $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — Số ngày Chung cho mèo ăn.

Dòng tiếp theo chứa $$$m$$$ số nguyên dương $$$a_1,a_2,\cdots,a_m$$$ ($$$1 \le a_i \le 10^9$$$)— Số cá Chung cho 2 con mèo ăn mỗi ngày.

Output

In ra một số nguyên duy nhất — số cá chệnh lệch tối đa nhỏ nhất đạt được, hoặc $$$-1$$$.

Examples
Input
5
4 7 4 3 2
Output
-1
Input
5
5 4 6 5 4
Output
3
Note

Ở ví dụ 2, ta có thể cho mèo ăn như sau

  • Ngày 1: Mèo A ăn $$$1$$$ con cá, mèo B ăn $$$4$$$ con cá.
  • Ngày 1: Mèo A ăn $$$1$$$ con cá, mèo B ăn $$$3$$$ con cá.
  • Ngày 1: Mèo A ăn $$$3$$$ con cá, mèo B ăn $$$3$$$ con cá.
  • Ngày 1: Mèo A ăn $$$3$$$ con cá, mèo B ăn $$$2$$$ con cá.
  • Ngày 1: Mèo A ăn $$$3$$$ con cá, mèo B ăn $$$1$$$ con cá.

Vậy chênh lệch số cá 2 con mèo ăn lần lượt là $$$3,2,0,1,2$$$. Chênh lệch lớn nhất trong các ngày là $$$3$$$.