Cho một dãy gồm $n$ số nguyên $A=(a_1,a_2,…,a_n)$. Ta định nghĩa: đoạn con của dãy $A$ là một dãy các phần tử liên tiếp nhau thuộc $A$. Hoặc có thể viết $(a_i,a_{i+1},…,a_j)$ là một đoạn con của $A$ với $i \leq j$. Độ dài của đoạn con được tính là số phần tử của đoạn con đó, ví dụ, đoạn con trên có độ dài là $j-i+1$.

Yêu cầu: Tìm một đoạn con có độ dài ngắn nhất chứa cả số lớn nhất và số nhỏ nhất của dãy $A$.

Input

• Dòng đầu chứa số nguyên dương $n \ (1 \leq n \leq 10^5)$.
• Dòng tiếp theo chứa $n$ số nguyên $a_1,a_2,….,a_n$.

Output

• Một số duy nhất là độ dài của đoạn con tìm được thỏa mãn yêu cầu đề bài.

Example

8
1 3 6 2 8 1 3 8 

2