Description

苏苏学姐最近想了好久，决定去幼儿园当老师，刚入园的第一天便被一个问题难住了，你能帮帮她吗QWQ？问题如下

n个小朋友围成一圈，按顺时针顺序依次编号为1∼n，其中第i个小朋友的身高为$a_i$。

请你找到两个相邻的小朋友，要求他们之间的身高差尽可能小。

请你输出身高差的最小可能值。

Format

Input

第一行包含整数n。

第二行包含n个整数$a_1,a_2,\cdots,a_n$。

Output

一个整数，表示身高差的最小可能值。

Samples

5
10 12 13 15 10

0

4
10 20 30 40

10

Hint

1. 小朋友i和小朋友j的身高差为$\vert a_i - a_j \vert$，也就是说身高差一定不为负。
2. 由于小朋友是围成一圈，所以1号小朋友和n号小朋友也是相邻的。

数据范围

2≤n≤100，1≤ai≤1000。