ami có một dãy số \(A\) độ dài \(N\) và một dãy số \(B\) gồm \(N\) số \(0\). Các bạn có thể thực hiện thao tác sau trên dãy \(B\) để biến dãy \(B\) thành \(A\):

• Chọn một cặp \((l, r)\) với \(1 ≤ l ≤ r ≤ n\) và một số nguyên \(k\). Sau đó, gán \(a_i = max(a_i , k)\) với mọi \(l ≤ i ≤ r\).

Định nghĩa "giá trị cuogma" của dãy số \(A\) chính là số thao tác ít nhất cần thực hiện lên dãy \(B\) để biển \(B\) thành \(A\). Ví dụ, nếu dãy \(A\) là [1 2 3] thì giá trị cuogma của dãy số này là 3:

• Chọn cặp (1, 1) và \(k\) = 1, dãy \(B\) trở thành [1 0 0].
• Chọn cặp (2, 3) và \(k\) = 2, dãy \(B\) trở thành [1 2 2].
• Chọn cặp (3, 3) và \(k\) = 3, dãy \(B\) trở thành [1 2 3] - chính là dãy \(A\).

Các bạn cũng có thể thực hiện thao tác sau trên dãy \(A\):

• Chọn một chỉ số \(i\) với \(1 ≤ i ≤ n\) và một số nguyên \(x ≥ a_i\). Sau đó, gán \(a_i = x\).

Hãy tìm cách thực hiện thao tác trên dãy \(A\) không quá 1 lần để giá trị cuogma của dãy kết quả là nhỏ nhất có thể và hãy in ra kết quả này.

Input

• Dòng đầu tiên chứa 1 số nguyên dương \(t\) là số lượng test case.

• Mỗi test case có dạng sau:

  • Dòng đầu tiên chứa 1 số nguyên dương \(N\) là số phần tử của \(A\).
  • \(N\) dòng tiếp theo chứa, mỗi dòng chứa 1 số nguyên dương biểu thị dãy số \(A\).

Output

• Giá trị cuogma nhỏ nhất của dãy \(A\) sau khi thực hiện biến đổi.

Scoring

• Tất cả test có \(1 \leq t \leq 3000\).
• Subtask \(1\) (\(50\%\) số điểm): \(\sum {N} \leq 100\) và \(a_i\) \(\leq\) \(3000\).
• Subtask \(2\) (\(50\%\) số điểm): \(\sum {N} \leq 3000\) và \(a_i\) \(\leq\) \(3000\).

Example

2
3
1
2
3
5
2 
2 
5 
2
4

2
3