Cho một dãy gồm \(n\) số nguyên \(A = (a_1, a_2, \dots, 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}, \dots, a_j)\) là một đoạn con của \(A\) với \(i \le j\). Độ dài của đoạn con được tính là số phần tử của đoạn con đó.

Yêu cầu: Tìm một đoạn con có độ dài ngắn nhất sao cho trong đoạn con có chứa cả phần tử lớn nhất và phần tử nhỏ nhất của dãy \(A\).

Input

• Dòng đầu chứa số nguyên dương \(T \le 10^5\) là số lượng bộ dữ liệu (test case).
• \(T\) nhóm dòng tiếp theo, mỗi nhóm gồm 2 dòng tương ứng với một test theo khuôn dạng:
  • Dòng 1 chứa số nguyên dương \(n\) (\(1 \le n \le 10^6\)).
  • Dòng 2 chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(\forall i: |a_i| \le 10^9\)).

Tổng các giá trị \(n\) trong toàn bộ \(T\) test không vượt quá \(10^6\).

Output

• Ghi ra ứng với mỗi test, ghi ra một số duy nhất trên một dòng là độ dài của đoạn con tìm được.

Example

4
8
1 3 6 2 8 1 3 8
10
1 2 3 1 8 5 9 6 4 9
8
1 1 1 1 1 1 1 1
7
1 2 3 4 5 3 1

2
4
1
3