Bạn được cho một mảng gồm ~n~ số nguyên dương. Nhiệm vụ của bạn là tìm hai số trong mảng sao cho ước chung lớn nhất (GCD) của chúng là lớn nhất có thể.

Dữ liệu vào Dòng đầu tiên chứa số nguyên ~n~ — kích thước của mảng.

Dòng thứ hai chứa n số nguyên ~x₁, x₂, ..., xₙ~ — các phần tử của mảng.

Dữ liệu ra In ra ước chung lớn nhất lớn nhất có thể tìm được từ hai phần tử bất kỳ trong mảng.

Ràng buộc

~2≤n≤2⋅10^5~

~1≤xi≤10^6~

Ví dụ :

Input:

5
3 14 15 7 9

Output:

7

Giải thích: Cặp số (14, 7) có GCD = 7 là lớn nhất trong tất cả các cặp có thể chọn.

Cho ~n~ số nguyên. Với mỗi số, bạn cần đếm xem nó có bao nhiêu ước số.

Ví dụ: với ~x = 18~, đáp án là 6, vì ước số của 18 là: 1, 2, 3, 6, 9, 18.

Dữ liệu vào:

Dòng đầu tiên chứa số nguyên ~n~ — số lượng số cần xử lý.

Tiếp theo là ~n~ dòng, mỗi dòng chứa một số nguyên ~x~.

Dữ liệu ra:

Với mỗi số ~x~, in ra số lượng ước số của nó, mỗi kết quả trên một dòng.

Ràng buộc:

~1≤n≤10^5~

~1≤x≤10^6~

Ví dụ :

Input:

3
16
17
18

Output:

5
2
6

Giải thích:

16 có ước số: 1, 2, 4, 8, 16 → 5 ước số

17 là số nguyên tố → chỉ có 1 và 17 → 2 ước số

18 có 6 ước như đã phân tích ở đầu bài.

Một hoán vị của các số nguyên từ ~1, 2, ..., n~ được gọi là "hoán vị đẹp" nếu không có hai phần tử liền kề nào có hiệu bằng 1.

Cho một số nguyên n, hãy tạo ra một hoán vị đẹp của dãy số từ 1 đến n nếu tồn tại. Nếu có nhiều đáp án, bạn có thể in ra bất kỳ một hoán vị nào. Nếu không tồn tại hoán vị đẹp, hãy in ra "NO SOLUTION".

Dữ liệu vào:

Dòng duy nhất chứa số nguyên ~n~.

Dữ liệu ra:

In ra hoán vị đẹp nếu có thể, mỗi số cách nhau bởi khoảng trắng.

Nếu không thể, in ra "NO SOLUTION".

Ví dụ 1:

Input:

5

Output:

4 2 5 3 1

Ví dụ 2:

Input:

3

Output:

NO SOLUTION

Giải thích:

Với ~𝑛= 5~ một hoán vị như 4 2 5 3 1 là hợp lệ, vì không có hai số liền kề nào chênh lệch đúng 1 đơn vị.

Với ~𝑛= 3~ không có cách nào để sắp xếp ba số sao cho không có cặp nào liền nhau có hiệu bằng 1.

Bạn được cho một mảng gồm ~n~ số nguyên. Nhiệm vụ của bạn là biến đổi mảng sao cho nó trở thành mảng không giảm, tức là mỗi phần tử không nhỏ hơn phần tử đứng trước nó.

Trong mỗi lần thao tác, bạn được phép tăng giá trị của một phần tử bất kỳ lên 1 đơn vị. Hãy tính số lần thao tác tối thiểu cần thiết để biến mảng thành mảng không giảm.

Dữ liệu vào:

Dòng đầu tiên chứa số nguyên ~n~ — kích thước của mảng.

Dòng thứ hai chứa n số nguyên ~x₁, x₂, ..., xₙ~ — các phần tử của mảng.

Dữ liệu ra:

In ra một số nguyên duy nhất — số lần thao tác tối thiểu.

Ràng buộc:

~1≤𝑛≤2⋅10^5~

~1 ≤𝑥≤10^9~

Input:

5  
3 2 5 1 7

Output:

5

Giải thích:

Tăng phần tử thứ 2 từ 2 → 3 (1 lần)

Tăng phần tử thứ 4 từ 1 → 5 (4 lần)

→ Tổng cộng: 1 + 4 = 5 lần để mảng trở thành [3 3 5 5 7] (không giảm).

Bạn được cho một chuỗi DNA — là một xâu chỉ gồm các ký tự A, C, G, và T. Nhiệm vụ của bạn là tìm độ dài của chuỗi con liên tiếp dài nhất mà chỉ gồm một loại ký tự duy nhất.

Dữ liệu vào:

Dòng duy nhất chứa một chuỗi gồm n ký tự (mỗi ký tự là A, C, G hoặc T).

Dữ liệu ra:

In ra một số nguyên duy nhất: độ dài của chuỗi con liên tiếp dài nhất chỉ gồm một ký tự duy nhất.

Ràng buộc:

~1≤n≤10^6~

Ví dụ :

Input:

ATTCGGGA

Output:

3

Giải thích: Chuỗi con "GGG" có độ dài 3 là chuỗi con liên tiếp dài nhất chỉ gồm ký tự 'G'.

Cho một mảng ~n~ số nguyên dương ~a[1], a[2], ..., a[n]~ ~(a[i] ≤ 1000).~

Hãy xác định số lượng phần tử khác nhau trong mảng có tần suất xuất hiện bằng tần suất cao nhất.

Input:

~-~Dòng đầu tiên là số nguyên ~n~ ~(1 ≤ n ≤ 10^5)~

~-~Dòng thứ hai gồm ~n~ số nguyên ~a[i]~ ~(1 ≤ a[i] ≤ 1000)~

Output: Một số nguyên duy nhất: số phần tử có tần suất xuất hiện bằng tần suất lớn nhất

Ví dụ :

Input:

10  
1 2 2 3 3 3 4 4 4 5

Output:

2

Giải thích:

Số 3 và 4 xuất hiện 3 lần, đây là tần suất lớn nhất mà chỉ có 2 số đạt tần suất này ~→~ Kết quả là 2.

Cho một mảng gồm ~n~ số nguyên. Trong đó, mọi số đều xuất hiện đúng 2 lần, ngoại trừ duy nhất một số xuất hiện 1 lần.

Hãy tìm số xuất hiện đúng ~1~ lần đó.

Input:

Dòng đầu tiên: số nguyên ~n~ (~1 ≤ n ≤ 1001~)

Dòng thứ hai: ~n~ số nguyên ~(|aᵢ| ≤ 10^6)~

Bảo đảm: chỉ có đúng một số xuất hiện một lần, các số còn lại xuất hiện đúng 2 lần.

Output: In ra số duy nhất đó.

Ví dụ :

Input:

7
1 2 3 2 3 1 4

Output:

4

Cho một mảng ~n~ số nguyên ~a₁, a₂, ..., aₙ~.

Một cặp số ~(aᵢ, aⱼ)~ được gọi là cặp đối kháng nếu ~aᵢ + aⱼ = 0~ và ~i < j~.

Hãy kiểm tra xem mảng có chứa ít nhất một cặp đối kháng không?

Input:

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

~-~ Dòng thứ hai là n số nguyên ~a₁, a₂, ..., aₙ~

Output:

In "YES" nếu tồn tại ít nhất một cặp đối kháng ~(aᵢ, aⱼ)~ với ~i < j~

In "NO" nếu không tồn tại cặp nào

Ví dụ:

Input:

5
0 2 5 4 9

Output:

NO

Cho một mảng gồm n số nguyên. Bạn được phép đổi vị trí các phần tử trong mảng (hoán đổi tự do). Hãy kiểm tra xem có thể sắp xếp lại mảng sao cho các vị trí chẵn (tính từ 0) chứa số chẵn và các vị trí lẻ chứa số lẻ hay không.

Input:

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 ≤ n ≤ 1000)~
• Dòng thứ hai chứa n số nguyên ~a₁, a₂, ..., aₙ~ ~(|aᵢ| ≤ 10⁶)~

Output:

• In ra "YES" nếu có thể sắp xếp lại như yêu cầu.
• In ra "NO" nếu không thể.

Ví dụ :

Input:

6
2 1 4 3 6 5

Output:

YES

→ Vì ta có thể sắp: ~2~ ~1~ ~4~ ~3~ ~6~ ~5~ → chỉ số chẵn là ~2~ ~4~ ~6~ (đều chẵn), chỉ số lẻ là ~1~ ~3~ ~5~ (đều lẻ)

Cho một mảng số nguyên gồm n phần tử. Hãy viết chương trình C++ để đếm xem có bao nhiêu số chính phương trong mảng đã cho.

Đầu vào

Dòng đầu tiên là số ~n~.

Dòng tiếp theo có ~n~ số.

Giới hạn

~1≤n≤500~

Các phần tử trong mảng là số nguyên dương không quá ~500~.

Đầu ra

Số lượng số chính phương có trong mảng.

Ví dụ :

Input:

5
1 4 8 6 5

Output:

1

Cho một mảng ~a~ gồm ~n~ số nguyên.

Một dãy được gọi là không nghịch biến đặc biệt nếu thỏa mãn điều kiện:

~-~ Dãy không giảm ( nghĩa là ~a[i] <= a[i+1]~ với mọi ~i~ )

~-~ Không tồn tại 3 phần tử liên tiếp bằng nhau.

Nhiệm vụ của bạn: Kiểm tra xem mảng đã cho có phải là dãy không nghịch biến đặc biệt hay không !

Đầu vào

Dòng đầu tiên là số ~n~.

Dòng tiếp theo có ~n~ số phần tử trong mảng.

Giới hạn

~1≤n≤500~

Các phần tử trong mảng là số nguyên dương không quá ~500~.

Đầu ra

In ra "YES" nếu thỏa mãn đề bài còn "NO" nếu ngược lại.

Ví dụ :

Input:

4
4 3 2 1

Output:

NO