Khoảng cách của một mảng a gồm n phần tử bằng phần tử lớn nhất trừ phần tử nhỏ nhất.

Bạn hãy viết chương trình nhập vào mảng a, in ra khoảng cách của mảng a.

Input

Gồm 2 dòng:

Dòng thứ nhất là số phần tử của mảng n (~n ≤ 10^5~)

Dòng thứ hai gồm n phần tử ~a_1~, ~a_2~, ... ~a_n~ (1 ≤ ~a_i~ ≤ ~10^5~)

Output

Một dòng duy nhất là khoảng cách của mảng a.

Examples

Input

5
4 3 6 1 9

Output

8 

Cho một mảng a có n phần tử ~a_0~, ~a_1~, ..., ~a_{n-1}~ và một số x. Bạn hãy in ra vị trí của x trong mảng a.

Chính xác hơn, hãy in ra vị trí i trong mảng với ~a_i~ = x. Các vị trí được in theo thứ tự tăng dần và chỉ số bắt đầu từ 0.

Input

Gồm 2 dòng.

Dòng thứ nhất là số nguyên n. (~n ≤ 10^5~)

Dòng thứ hai gồm n số ~a_0~, ~a_1~, ..., ~a_{n-1}~. (1 ≤ ~a_i~ ≤ ~≤ 10^3~)

Output

Một dòng duy nhất là vị trí của x trong mảng a và cách nhau bởi dấu cách. Nếu x không xuất hiện trong mảng a thì không in ra gì.

Examples

Input

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

Output

0 5 7

Sau khi học trên các lớp traning về hàm và chương trình con thì các bạn sinh viên muốn làm nhiều bài tập về chủ đề này hơn để thuần thạo khả năng code của mình.

Ở bài này, bạn nhận được một mảng có N phần tử và Q thao tác đảo ngược mảng.

Thao tác đảo ngược mảng được hiểu như sau:

Ở mỗi thao tác, bạn sẽ nhận được hai số là L và R đại diện cho đoạn mảng con từ phần tử thứ L đến phần tử thứ R. Sau đó, bạn phải thay đổi đoạn mảng con đó bằng cách đảo ngược lại để được thứ tự mới.

Ví dụ:

Đoạn mảng con đó là A[L], A[L+1], ... A[R-1], A[R] thì đoạn mảng con đó sẽ được đảo ngược lại thứ tự là: A[R], A[R-1], ...A[L+1], A[L].

Do có nhiều thao tác nên bạn phải bắt buộc đảo ngược mảng theo thứ tự lần lượt Q thao tác đấy, có nghĩa là phải đạo được đoạn L1, R1 -> L2,R2...->LQ, RQ.

Thực hiện xong bạn in ra mảng với thứ tự cuối cùng đạt được

Input

Dòng đầu tiên chứa hai số nguyên N (N ≤ ~10^5~) và Q (Q ≤ ~100~) đại diện cho số lượng phần tử mảng và Q thao tác.

Dòng thứ hai chứ N số nguyên dương (A[i] ≤ ~10^9~ ).

Q dòng tiếp theo chứa hai số nguyên Li, Ri để mô tả đoạn mảng con thứ i cần phải đảo có thứ tự từ L -> R (1 ≤ L < R ≤ N).

Output

In ra một dòng duy nhất các giá trị mảng với thứ tự được thay đổi sau cùng.

Examples

Input

5 2
1 2 3 4 5
2 4
4 5

Output

1 4 3 5 2

*Giải thích: * Thứ tự mảng sau khi đổi từ vị trí 2 đến 4 là: 1 4 3 2 5. Sau đó đổi tiếp tục từ vị trí 4 đến 5 sẽ được: 1 4 3 5 2.

Gợi ý: Có thể áp dụng chương trình con để viết với chức năng đảo thứ tự từ phần tử thứ L-> R, và mỗi lần nhập L, R thì ta gọi hàm để thực hiện.

Mô tả vấn đề

Sử dụng mảng một chiều X[100] để lưu các số nguyên. Viết các hàm thực hiện các yêu cầu sau:

• Tính giá trị trung bình của mảng: m = ~\frac{x_0 + x_1 + x_2 + ... + x_{(n-1)}}{n}~

• Tính tổng bình phương: s = ~x_0^2~ + ~x_1^2~ + ~x_2^2~ + ... + ~x_{n-1}^2~

• Tính phương sai (Variance) d~^2~ = ~\frac{s}{n}~ - m~^2~

Input

Input gồm 2 dòng:

Dòng thứ nhất chứa duy nhất một số nguyên n (n ≤ 100)

Dòng thứ hai chứa n phần tử x~_0~, x~_1~, x~_2~, ..., x~_{n-1}~ của mảng

Output

Gồm 3 dòng:

Dòng thứ nhất là giá trị trung bình của mảng x. Làm tròn đến 1 chữ số thập phân.

Dòng thứ hai là tổng bình phương của mảng x.

Dòng thứ ba là phương sai của mảng x. Làm tròn đến 3 chữ số thập phân.

Sample Input 1

3
1 2 3

Sample Output 1

2.0
14
0.667

Cho mảng a gồm có n phần tử ~a_0~, ~a_1~, ... ~a_{n-1}~ và một số nguyên k. Hãy in ra phần tử lớn thứ k của mảng a sau khi đã sắp sếp tăng dần.

Lưu ý là chỉ số bắt đầu từ 0.

Input

Gồm 2 dòng:

Dòng thứ nhất là số phần tử của mảng n và số k (~1 ≤ n ≤ 10^3~, 0 ≤ k ≤ n-1)

Dòng thứ hai gồm n số nguyên ~a_0~, ~a_1~, ... ~a_{n-1}~.

Output

Một dòng duy nhất là số lớn thứ k của mảng a.

Examples

Input

8 3  
4 2 6 3 6 4 5 7 

Output

4 

Mảng sau khi đã sắp sếp tăng dần là: 2, 3, 4, 4, 5, 6, 6, 7. Vì vậy phần tử lớn thứ 3 là 4 (chỉ số bắt đầu từ 0)

Mô tả vấn đề

Dãy fibonaci là dãy số như sau:

f[1] = f[2] = 1

f[i] = f[i-1] + f[i-2] (i >= 3)

Bạn hãy viết chương trình thực hiện các yêu cầu sau:

• Sử dụng mảng A, lưu n giá trị đầu tiên của dãy Fibonacci.
• In n giá trị đầu tiên của dãy Fibonacci ra màn hình.

Input

Nhập số nguyên n (n ≤ 40)

Output

Xuất mảng A. Mỗi phần tử in trên một dòng

Sample Input 1

5

Sample Output 1

1 
1 
2
3
5

Trọng và Bảo đang chơi 1 trò chơi. Trò chơi này sẽ có n cái hố . Mỗi cái hố sẽ có một số lượng các viên bi, mỗi hố có số lượng bi khác nhau, không hố nào giống hố nào. Luật trò này rất đơn giản. Tới lượt của ai thì người đó sẽ chọn cái hố nằm ở bên trái ngoài cùng hoặc bên phải ngoài cùng và lấy tất cả số viên bi nằm trong cái hố đó. Biết Bảo là người đi đầu tiên. Tới cuối cùng, ai có nhiều bi hơn thì người đó thắng

Đã chơi thì phải thắng nên cả 2 người đều quyết định chọn tham lam tức tối ưu nhất ở thời điểm hiện tại.

Yến là 1 người bạn của 2 người, cô ấy biết được chiến thuật của 2 người này và muốn bạn giúp cô ấy xác định kết quả cuối cùng.

Input
Dòng đầu tiên chứa 1 số nguyên n (1≤n≤1000) — số lượng cái hố. Dòng thứ hai chứa n số nguyên, được ngăn cách bởi 1 khoảng trắng, là số lượng các viên bi ở trong n cái hố đó. Mỗi cái hố đều có số lượng bi khác nhau và nằm trong khoảng từ 1 đến 1000.

Output
In 1 dòng duy nhất chứa 2 số nguyên được cách nhau bởi 1 khoảng trắng. Đó lần lượt là điểm của Bảo và Trọng lúc kết thúc trò chơi

Examples
Input

4
4 1 2 10

Output

12 5

Input

7
1 2 3 4 5 6 7

Output

16 12

Note
Ở ví dụ đầu tiên, Bảo đã chọn những cái hố có số lượng bi là 10 và 2, Vậy Bảo có 12 viên. Còn Trọng thì chọn cái hố có số lượng bi là 4 và 1, vậy tổng viên bi của Trọng là 5.

Mô tả vấn đề

Cho hai mảng A, B là hai tập hợp, cả 2 có kích thước n nhập từ bàn phím. Tạo mảng C là một tập hợp gồm các phần tử:

• Xuất hiện trong cả A và B.

• Xuất hiện trong A nhưng không xuất hiện trong B.

• Xuất hiện trong B nhưng không xuất hiện trong A.

Input

Dòng thứ nhất là một số duy nhất n (n ≤ 100).

Dòng thứ hai là các phần tử A~_1~, A~_2~, ... A~_n~ của mảng A (1 ≤ ~A_i~ ≤ 1000).

Dòng thứ ba là các phần tử B~_1~, B~_2~, ... B~_n~ của mảng B (1 ≤ ~B_i~ ≤ 1000) ..

Output

Gồm 3 dòng:

Dòng thứ nhất là các phần tử xuất hiện trong cả A và B.

Dòng thứ hai là các phần tử xuất hiện trong A nhưng không xuất hiện trong B.

Dòng thứ ba là các phần tử xuất hiện trong B nhưng không xuất hiện trong A.

Đảm bảo tất cả các phần tử trong mảng A và B là phân biệt.

Sample Input 1

5 
1 2 3 4 5 
3 4 8 9 1

Sample Output 1

1 3 4
2 5
8 9

Được biết, các bạn nữ rất ngưỡng mộ bạn nam nào vừa học IT vừa giỏi tiếng anh.

Một bạn nữ rất xinh đẹp đã nhờ bạn làm 1 bài tập. Đó là in ra chữ tiếng anh của 1 số nguyên

Input
Dòng duy nhất chứa 1 số nguyên s (0≤s≤99).

Output
Dòng duy nhất chứa 1 một dòng chữ, là chữ tiếng anh của số s đã cho, không viết hoa và có hoặc không có dấu ('-') tùy số. Lưu ý: không dùng khoảng trắng (space).

Examples
Input

6

Output

six

Input

99

Output

ninety-nine

Input

20

Output

twenty

Note
Tất tần tật về cách viết số trong tiếng anh http://en.wikipedia.org/wiki/English_numerals .

Có 1 cái sàn nhà hình chữ nhật có diện tích M×N ô vuông. Bạn được cho vô hạn các viên gạch có diện tích chuẩn là 2×1 ô vuông. Biết rằng bạn có thể lắp các viên gạch ấy vào cái sàn theo chiều dọc hoặc chiều ngang, hãy tìm số lượng các viên gạch lớn nhất sao cho thỏa các yêu cầu sau đây:

1. Mỗi viên gạch sẽ lấp đầy 2 ô vuông.

2. Không có viên gạch nào bị chồng lên nhau.

3. Các viên gạch nằm hoàn toàn ở bên trong cái sàn. Và được phép chạm các cạnh của cái sàn.

Input
1 dòng duy nhất chứa 2 số M và N — diện tích của cái sàn dưới đơn vị là ô vuông (1≤M≤N≤16).

Output
In ra 1 dòng duy nhất chứa 1 số nguyên — số lượng các viên gạch lớn nhất tính được.

Examples
Input

2 4

Output

4

Input

3 3

Output

4

Sau sự cố tình yêu lần trước David đã bị trầm cảm. Cậu ấy không thể tính bất cứ thứ gì ? . Một hôm cô giáo giao cho anh ấy bài tập về nhà kiểm tra số nguyên tố. Lần này không phải kiểm tra 1 số mà là t số nguyên. Hãy giúp David làm bài tập này ?

Số nguyên tố là số chỉ chia hết cho 1 và chính nó

Input

Dòng đầu tiên chứa một số nguyên t ~(1 ≤ t ≤ 100)~ - số lượng test case trong dữ liệu đầu vào. Sau đó, t các trường hợp kiểm tra theo sau.

Mỗi test case là một dòng chứa số nguyên n ~( 0 ≤ n ≤ 10^{10})~.

Output

Đầu ra là "YES" nếu đó là số nguyên tố ngược lại thì in "NO".

*Example 1 *

Input

3
5
6
7

Output

YES
NO
YES

Một số nguyên dương (lớn hơn 0) được gọi là tròn nếu nó có dạng d00 ... 0. Nói cách khác, một số nguyên dương là tròn nếu tất cả các chữ số của nó ngoại trừ chữ số tận cùng bên trái (có nghĩa nhất) đều bằng không. Đặc biệt, tất cả các số từ 1 đến 9 (bao gồm) đều làm tròn.

Ví dụ, các số sau là tròn: 4000, 1, 9, 800, 90. Các số sau không tròn: 110, 707, 222, 1001.

Bạn được cung cấp một số nguyên dương n ~(1 ≤ n ≤ 10^4)~. Biểu diễn số n dưới dạng tổng của các số làm tròn bằng cách sử dụng số lượng tối thiểu của các tổng (phụ). Nói cách khác, bạn cần biểu diễn số n đã cho dưới dạng tổng của số hạng ít nhất, mỗi số là một số tròn chục.

Input

Dòng đầu tiên chứa một số nguyên t ~(1 ≤ t ≤ 10^4)~ - số lượng test case trong dữ liệu đầu vào. Sau đó, t các trường hợp kiểm tra theo sau.

Mỗi test case là một dòng chứa số nguyên n ~( 1 ≤ n ≤ 10^4)~.

Output

Đầu ra là các số tròn theo thứ tự từ nhỏ đến lơn và số lượng các số tròn (Lưu ý tổng các số tròn == n)

*Example 1 *

Input

3
5009
7
9876

Output

9 5000
2
7
1
6 70 800 9000
4

Mô tả vấn đề

Viết chương trình nhập một dãy số nguyên A có n phần tử từ bàn phím. In ra số lượng số nguyên tố có trong mảng.

*Note: * Số nguyên tố là số lớn hơn hoặc bằng 2, và có chia hết cho 1 và chính nó.

Input

Dòng đầu tiên là số nguyên n (n ≤ 1000).

Dòng thứ hai là dãy các số nguyên ~A1~, ~A2~, ... ~An~ (1 ≤ ~Ai~ ≤ 10000)

Output

In ra kết quả

Sample Input

6
2 6 7 10 5 4

Sample Output

3

Có 3 số nguyên tố trong mảng là 2, 7, 5.

Cho một mảng a gồm n phần tử ~a_1~, ~a_2~, ...~a_n~. Trong một bước bạn có thể tăng giá trị của một phần tử bất kỳ trong mảng lên 1 đơn vị. Bạn hãy tính số bước ít nhất để tạo ra mảng a gồm các phần tử tăng dần.

Mảng a tăng dần là mảng có các phần tử ~a_1~ ≤ ~a_2~ ≤ ... ≤ ~a_n~

Input

Gồm 2 dòng:

Dòng thứ nhất là một số nguyên n.(1 ≤ ~n ≤ 10^5~)

Dòng thứ hai là dãy số ~a_1~, ~a_2~, ...~a_n~ cách nhau bởi dấu cách. (1 ≤ ~a_i~ ≤ ~10^9~)

Output

Một dòng duy nhất là

Examples

Input

6
3 1 5 4 8 9 

Output

3 

*Note: *chúng ra tăng phần tử thứ 2 lên 2 đơn vị, phần tử thứ 4 lên 1 đơn vị.

Một anh tên Nước Uống Tinh Khiết Đóng Chai thích một chị tên M giấu tên. Nước Uống Tinh Khiết Đóng Chai thắc mắc không biết rằng chị M có thích mình hay không? Vì vậy Nước Uống Tinh Khiết Đóng Chai đã dùng một cách đó là bói tình yêu. Nước Uống Tinh Khiết Đóng Chai hái bông hoa bên đường và ngắt từng cánh hoa một. Sau khi ngắt mỗi cánh hoa, Nước Uống Tinh Khiết Đóng Chai sẽ bắt đầu bằng "Thích", sau đó nói xen kẽ "Thích" và "Không thích". Có n bông hoa quen đường, mỗi bông hoa có ~a_1~, ~a_2~, ... ~a_n~ cánh hoa. Nước Uống Tinh Khiết Đóng Chai muốn chọn một số bông hoa sao cho tổng số cánh hoa là lớn nhất đồng thời kết quả vẫn là "Thích". Hãy giúp Nước Uống Tinh Khiết Đóng Chai tìm tổng số cánh hoa lớn nhất có thể.

Input

Gồm 2 dòng:

Dòng thứ nhất là số phần tử của mảng n (~1 ≤ n ≤ 10^5~)

Dòng thứ hai gồm n số nguyên ~a_0~, ~a_1~, ... ~a_{n-1}~ ( 1 ≤ ~a_i ≤ 10^9~)

Output

Một dòng duy nhất là số cánh lớn nhất sao cho kết quả bói tình yêu là "Thích". Nếu không có kết quả là "Thích", hãy in ra "Simple" để thay thế.

Examples

Input

5
2 5 3 4 2

Output

13 

Note: * *Nước Uống Tinh Khiết Đóng Chai sẽ chọn những bông hoa có số cánh là 2, 5, 4, 2

Input

1
4

Output

Simple 

Note: Nước Uống Tinh Khiết Đóng Chai không thể chọn bất cứ bông hoa nào vì vậy in ra "Simple"

*Giới thiệu: Birthday version 1 *

L.G.N đang thu thập tiền xu. Hiện tại trên thế giới chỉ có ~N~ loại đồng tiền xu khác nhau, L.G.N có ~K~ trong số chúng. Anh ấy sẽ tổ chức sinh nhật sớm, vì vậy tất cả những người bạn ~M~ của anh ấy đã quyết định tặng anh ấy tiền xu. Tất cả đều đồng ý với ba điều kiện sau:

1. Mọi người phải tặng số lượng tiền xu như nhau.
2. Tất cả các đồng tiền xu được trao cho L.G.N phải khác nhau.
3. Tổng cộng không dưới ~L~ xu từ quà tặng, và phải có được ít nhất ~L~ xu mới trong bộ sưu tập của L.G.N.

Nhưng bạn bè của anh ấy không biết L.G.N đã có những đồng xu nào trong bộ sưu tập của mình. Họ không muốn tiêu nhiều tiền vì vậy họ muốn mua số lượng tiền xu tối thiểu, đáp ứng tất cả các điều kiện trên, bất kể bộ sưu tập của L.G.N. Giúp họ tìm số lượng xu tối thiểu này hoặc xác định rằng không thể đáp ứng tất cả các điều kiện.

Input

Đầu vào duy nhất chứa 4 số nguyên ~N, M, K, L (1≤K≤N≤10^{18}; 1≤M, L≤10^{18})~ - số lượng tiền xu khác nhau, số lượng bạn bè của L.G.N, kích thước bộ sưu tập của L.G.N và số lượng tiền xu, đó hẳn là thứ mới trong bộ sưu tập của L.G.N.

Output

In một số - số xu tối thiểu mà một người bạn có thể tặng để đáp ứng tất cả các điều kiện. Nếu không thể thỏa mãn cả ba điều kiện thì in ~-1~.

Examples

Input

20 15 2 3

Output

1

Input

10 11 2 4

Output

-1

Ghi chú:

Trong test thử nghiệm đầu tiên: mỗi người bạn một đồng xu là đủ, vì anh ta sẽ được tặng 15 đồng xu khác nhau và 13 trong số đó chắc chắn sẽ là xu mới.

Trong test thứ hai: thầy Lưu Giang Nam có 11 bạn, nhưng chỉ có 10 đồng xu khác nhau. Vì vậy, tất cả bạn bè không thể tặng anh ta những đồng xu khác nhau.

*Giới thiệu: Birthday version 2 *

AI club có một chú mèo tên là Miu Miu, và bạn có một bộ 9 loại nến bánh sinh nhật. Mỗi loại như vậy đại diện cho một chữ số từ 0 đến 9.

Cho các số 10 số nguyên ~c0, c1, c2, c3, c4, c5, c6, c7, c8, c9~, và ~c0~ là số lượng chữ số 0, ~c1~ là số lượng nến là chữ số 1, ~c2~ là số lượng chữ số 2, tương tự với ~c3, c4~..

Những chữ số này là cần thiết để chúc con mèo của AI club một sinh nhật vui vẻ. Đối với mỗi sinh nhật, bắt đầu với ngày đầu tiên, bạn muốn soạn tuổi của Miu Miu bằng cách sử dụng các chữ số từ tập hợp nến đã cho.

Vì bạn thắp nến trong thời gian rất ngắn, nên nến không có thời gian để cháy hết. Vì lý do này, bạn có thể sử dụng lại nến với số lần tùy ý (do đó bộ nến của bạn không bao giờ thay đổi).

Ví dụ: Trường hợp của mỗi chữ số chỉ có một nến (tức là ~c0 = c1 = ⋯ = c9 = 1~) thì bạn có thể soạn bất kỳ số nào từ 1 đến 10 bằng bộ này, nhưng bạn không thể soạn 11. vì chỉ có 1 ngọn nến là chữ số 1

Bạn phải xác định sinh nhật đầu tiên mà bạn không thể xác định tuổi của mèo bằng cách sử dụng bộ nến đã cho. Nói cách khác, hãy tìm số ~y~ nhỏ nhất sao cho tất cả các số từ ~1~ đến ~y-1~ có thể được tạo bởi các nến chữ số, nhưng không thể tạo được số ~y~.

Input

Dòng duy nhất của mỗi trường hợp thử nghiệm chứa 10 số nguyên ~c0, c1,…, c9 (0≤ci≤10^{5}~) - số nến 0, nến 1, 2 nến, v.v.

Đảm bảo rằng tổng của tất cả ci trong đầu vào không vượt quá ~10^{6}~.

Output

Đối với mỗi trường hợp thử nghiệm, hãy xuất một số nguyên trong một dòng - độ tuổi tối thiểu mà nến từ tập hợp của bạn không thể tạo thành.

Examples

Input

1 1 1 1 1 1 1 1 1 1

Output

11

Input

0 0 1 1 2 2 3 3 4 4

Output

1

Input

1 2 1 2 1 3 1 0 0 0

Output

7

Ghi chú: Không có ghi chú để ghi chú:))

Giới thiệu: Đây là một vấn đề đặc biệt

Đối với những bạn Accepted đầu tiên thì liên hệ với tác giả để nhận quà =))

Đề bài ở khắp mọi nơi⭐

Input

Đầu vào chứa một số nguyên duy nhất là ~a~ (~1 ≤ a ≤ 19000~).

Output

Đầu ra là một số nguyên (~1 ≤ output ≤ 3.10^{9}~).

Examples

Input

2

Output

13

Input

3

Output

37

Là một người tài năng giấu tên, anh ấy có rất nhiều huy chương vàng, bạc, đồng, tương ứng với mỗi loại sẽ được đánh số là 1, 2 ,3.

Là một người nhạy cảm nên lúc nào anh ấy cũng muốn các huy chương của mình được sắp xếp tăng dần theo số trên mặt huy chương. Để sắp lại đống huy chương anh ấy quyết định làm một trò chơi như sau:

Một lần anh ấy sẽ chọn ra 2 chiếc huy chương và đổi chỗ chúng cho nhau tức chọn hai số ai và aj (i<j) và đổi chỗ chúng <br>
Hỏi anh ấy phải mất ít nhất bao nhiêu lần như vậy để sắp xếp đống huy chương theo thứ tự tăng dần??

Input
Dòng đầu tiên chứa 1 số nguyên n (1≤n≤1000) — số lượng huy chương. Dòng thứ hai chứa n số nguyên ai (1<= ai <=3), được ngăn cách bởi 1 khoảng trắng.

Output
In 1 dòng duy nhất là số lần thực hiện ít nhất.

Examples
Input

9
2 2 1 3 3 3 2 3 1

Output

4

Note
2 2 1 3 3 3 2 3 1 -> 1 2 2 3 3 3 2 3 1

1 2 2 3 3 3 2 3 1 -> 1 2 2 1 3 3 2 3 3

1 2 2 1 3 3 2 3 3 -> 1 1 2 2 3 3 2 3 3

1 1 2 2 3 3 2 3 3 -> 1 1 2 2 2 3 3 3 3

Input

Đầu vào chứa 2 số nguyên duy nhất là ~a~, ~b~ (~1 ≤ a, b ≤ 10^{18}~).

Output

Đầu ra là một số nguyên.

Examples

Input

2 13

Output

33

Input

100 700

Output

107

Cho một mảng a gồm n phần tử ~a_1~, ~a_2~, ... ~a_n~.

Gọi độ bất ngờ của x trong mảng a là số lần xuất hiện của x trong mảng a.

Bây giờ bạn hãy in ra độ bất ngờ của mỗi phần tử ~a_1~, ~a_2~, ... ~a_n~.

Input

Dòng duy nhất chứa một số nguyên n

Dòng thứ hai là dãy ~a_1, a_2, ... a_n ~

Subtask 1 (60% điểm): ~1 ≤ n ≤ 10^3, 1 ≤ a_i ≤ 10^3~

Subtask 2 (40% điểm): ~1 ≤ n ≤ 10^5, 1 ≤ a_i ≤ 10^5~

Output

Một dòng duy nhất là độ bất ngờ của mỗi phần tử ~a_1, a_2, ... a_n~.

Examples

Input

9 
1 3 2 4 5 1 2 2 5 

Output

2 1 3 1 2 2 3 3 2 

Cho một mảng a gồm n phần tử ~a_1~, ~a_2~, ... ~a_n~.

Gọi độ bất ngờ của x trong mảng a là số lần xuất hiện của x trong mảng a.

Giá trị v được gọi là giá trị tăng động khi và chỉ khi độ bất ngờ của v trong mảng a là lớn nhất. Ví dụ mảng a = [1, 3, 2, 1, 4, 1, 2], thì 1 là tăng động vì có độ bất ngờ là 3 và là độ bất ngờ lớn nhất. Còn mảng [1, 2, 2, 1] có hai phần tử 1 và 2 đều có độ bất ngờ là 2 nên mảng a không có giá trị tăng động.

Bây giờ bạn hãy tìm mảng con có giá trị tăng động sao cho độ dài của mảng con là nhỏ nhất.

Mảng con là dãy các phần tử liên tiếp ~a_l~, ~a_{l+1}~, ... ~a_r~ sao cho (1 ≤ l ≤ r ≤ n)

Input

Dòng đầu tiên là số test case t (2 ≤ t ≤ 5).

Mỗi test case gồm hai dòng:

Dòng thứ nhất chứa một số nguyên n.

Dòng thứ hai là dãy ~a_1, a_2, ... a_n ~

Subtask 1 (35% điểm): ~1 ≤ n ≤ 10^2, 1 ≤ a_i ≤ 10^2~

Subtask 2 (35% điểm): ~1 ≤ n ≤ 10^3, 1 ≤ a_i ≤ 10^3~

Subtask 3 (30% điểm): ~1 ≤ n ≤ 10^5, 1 ≤ a_i ≤ 10^5~

Output

Gồm t dòng, mỗi dòng là câu trả lời của mỗi test case tương ứng - độ dài mảng con nhỏ nhất và có giá trị tăng động.

Examples

Input

3
7
1 3 2 4 5 1 2
3
1 2 3
5
1 2 3 2 1

Output

5
-1
3