Trên trục tọa độ ~Ox~ có ~n~ điểm xanh và ~n~ điểm đỏ. Điểm xanh thứ ~i~ có tọa độ ~b_i~, điểm đỏ thứ ~i~ có tọa độ ~r_i~.

Với hai điểm có tọa độ ~x_1~ và ~x_2~, ta định nghĩa khoảng cách giữa hai điểm đó là ~|x_2 - x_1|~.

Hãy tìm khoảng cách nhỏ nhất giữa một cặp điểm xanh và điểm đỏ bất kì trong số các điểm đã cho.

Input

Dòng đầu tiên gồm số nguyên ~n~ (~1 ≤ n ≤ 10^5~) - số điểm xanh và cũng là số điểm đỏ.

Dòng thứ hai gồm ~n~ số nguyên ~b_1, b_2, . . . , b_n~ (~1 ≤ b_i ≤ 10^9~) tọa độ của điểm xanh

Dòng thứ ba gồm ~n~ số nguyên ~r_1, r_2, . . . , r_n~ (~1 ≤ r_i ≤ 10^9~) tọa độ của điểm đỏ

Output

In ra khoảng cách nhỏ nhất giữa một cặp điểm xanh và điểm đỏ bất kì.

Test mẫu

Input

1
2
6

Output

4

Input

2
1 7
10 5

Output

2

Scoring

Subtask 1 (~50\%~ số test): ~n ≤ 1000~

Subtask 2 (~50\%~ số test): Không có giới hạn gì thêm

Tính SoD một số nguyên dương sẽ được thể hiện bởi chuỗi công việc sau:

• Bước 1: Tính tổng các chữ số của số đó. • Bước 2: Kiểm tra nếu kết quả là một số có nhiều hơn hai chữ số thì ta sẽ thực hiện lại chuỗi công việc này cho tới khi kết quả là 1 chữ số.

Ví dụ: ~901 → 9 + 0 + 1 = 10 → 1 + 0 = 1~. Do vậy ~SoD(901) = 1~.

Bạn được cho một số nguyên dương ~N~, bạn hãy tính SoD của ~N~ giai thừa (~SoD(N!)~).

Input

Dòng thứ nhất chứa số nguyên ~T~ (~1 ≤ T ≤ 10^5~) - số lượng test.

~T~ dòng tiếp theo mỗi dòng sẽ chứa một số nguyên ~N~ (~0 ≤ N ≤ 10^{18}~)

Output

Gồm ~T~ số nguyên là kết quả của bài toán

Test mẫu

Input

4
1
3
5
13

Output

1
6
3
9

Giải thích Ở 2 ví dụ đầu, ta có thể thấy kết quả của 1! và 3! đều đã là số có một chữ số: 1; 6.

Ở ví dụ thứ ba, SoD(5!) = 1 + 2 + 0 = 3.

Scoring

T sẽ không có ràng buộc cho các subtask.

Subtask 1 (~20\%~ số test): ~0 ≤ N ≤ 10.~

Subtask 2 (~80\%~ số test): Không ràng buộc gì thêm.

Có ~n~ chiếc cột xếp thành 1 hàng với độ cao của các cột lần lượt là ~h_1, h_2, ..., h_n~.

Bây giờ, bạn cần xây một bể chứa nước thoả mãn các điều kiện sau:

• Hai thành của bể nước (thành bên trái và thành bên phải) là 2 trong ~n~ cột có sẵn • Giả sử 2 cột được chọn làm thành bể là cột ~i~ và cột ~j~ thì lượng nước chứa được là: ~min(h_i, h_j) × (|j - i| - 1)~

Do phải làm việc căng thẳng nên nhu cầu về nước của bạn khá lớn. Do đó, bạn muốn chọn cách dựng bể để chứa được nhiều nước nhất có thể.

Input

Dòng thứ nhất ghi số ~n~ là số cột cho sẵn (~2 ≤ n ≤ 10^5~)

Dòng thứ hai ghi ~n~ số ~h_1, h_2, ..., h_n~(~0 ≤ h_i ≤ 10^9~)

Output

Một dòng duy nhất in lượng nước lớn nhất mà bể nước có thể chứa được.

Test mẫu

Input

5
6 3 7 5 2

Output

10

Scoring

Subtask 1 (~50\%~ số test): ~n ≤ 1000~

Subtask 2 (~50\%~ số test): Không có ràng buộc gì thêm