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