Bạn có một dãy ADN: một xâu kí tự chỉ gồm các chữ cái A, T, G, C. Hãy tìm đoạn ADN con dài nhất chỉ gồm các kí tự giống nhau.

Input: Một dòng duy nhất chứa xâu ~s~.

Output: In ra độ dài của đoạn ADN con dài nhất tìm được.

Constraints: 1 ~\leq~ n ~\leq~ ~10^6~

Ví dụ:

Input                           Output
ATTCGGGA                        3

Con ốc sên đang ở gốc một cái cây cao v mét tính từ gốc. Ốc sên muốn bò lên ngọn cây để ăn những lá non trên đó. Ban ngày ốc sên bò được a mét lên trên, nhưng ban đêm khi ngủ nó bị trôi xuống b mét.

Yêu cầu: Cho các số nguyên ~a~, ~b~, ~v~, ~(1 <= b < a <= v <= 10^9)~. Hãy xác định số ngày cần thiết để ốc sên lên tới ngọn cây.

Ví dụ:

        INPUT               OUTPUT

        2 1 5                4

Đếm xem có bao nhiêu phần tử có giá trị lớn hơn hoặc bằng trung bình cộng của dãy số, liệt kê các phần tử này.

Ví dụ:

            INPUT                       OUTPUT
            6                           21 17 19
            11 21 15 17 13 19           3 16

Tìm giá trị nhỏ nhì (nếu có) của dãy số và đưa ra các vị trí đạt giá trị đó. Nếu không có thì ghi ra -1.

Ví dụ:

            INPUT                   OUTPUT

            6                       4
            1 3 4 2 7 3

Cho số n, tìm số Fibonacci thứ n và hiển thị dãy sô.

Ví dụ:

                INPUT                       OUTPUT

                30                          832040
                                            1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 

Một lời quảng cáo chào hàng trong một hiệu sách "mua 3, tặng 1, trả tiền 2". Vì vậy, mỗi khách mua ba quyển sẽ được tặng một quyển có giá rẻ nhất trong ba quyển. Và tất nhiên, khách hàng có thể mua nhiều sách, phụ thuộc vào việc sắp xếp các quyển sách vào mỗi nhóm ba quyển để được miễn phí quyển có giá rẻ nhất trong nhóm đó. Ví dụ, khách hàng lấy các quyển sách có giá 10, 3, 2, 4, 6, 4, 9. Nếu các quyển sách được sắp thành các nhóm: (10,3,2), (4,6,4) và (9) thì khách hàng ấy sẽ được tặng cuốn sách có giá là 2 trong nhóm một, 4 trong nhóm hai, và không có quyển sách nào được tặng trong nhóm ba vì nhóm này chỉ có 1 quyển.

Cô bán hàng là một người tốt bụng vì vậy cô ấy luôn muốn mỗi khách hàng trả ít tiền nhất có thể.

Yêu cầu: Cho giá các quyển sách, hãy giúp cô bán hàng sắp xếp các quyển sách vào các nhóm sao cho tổng số tiền khách hàng phải trả là ít nhất có thể. Chú ý cô bán hàng có thể sắp xếp các quyển sách vào các nhóm có ít nhất 1 quyển hoặc nhiều nhất 3 quyển.

Input:

• Dòng 1 gồm một số nguyên N (N <= 10~^5~) - là số sách khách hàng mua.
• N dòng tiếp theo mỗi dòng ghi một số nguyên Ai (Ai <= 10~^9~) - là giá mỗi quyển sách. Các số trên một dòng của input file được ghi cách nhau bởi dấu cách.

Output: Ghi ra một số nguyên duy nhất là giá tiền nhỏ nhất mà khách hàng phải trả.

Scoring:

• Subtask 1 (50% số điểm): N <= 2000.
• Subtask 2 (50% số điểm): không có ràng buộc gì thêm.

Ví dụ:

Input                           Output
4                               8
3
2
3
2 

----------

6                               21
6
4
5
5
5
5 

Cho một danh sách N số nguyên dương, nhiệm vụ của bạn là đếm số cặp số nguyên mà nguyên tố cùng nhau (tức là, ước số chung lớn nhất của chúng là một).

Input:

• Dòng đầu vào đầu tiên có một số nguyên n: số lượng phần tử.
• Dòng tiếp theo có n số nguyên x1, x2, ..., xn: nội dung của danh sách.

Output: In một số nguyên: câu trả lời cho nhiệm vụ.

Constraints:

• 1 <= n <= 10~^5~
• 1 <= xi <= 10~^6~

Ví dụ:

Input                           Output
8                               19
5 4 20 1 16 17 5 15

Cho dãy số nguyên dương gồm ~N~ phần tử ~a_1, a_2, \dots, a_N~ và số nguyên dương ~K~.
Chọn ra ~K~ phần tử liên tiếp sao cho tổng của chúng là lớn nhất. In ra giá trị đó.

Đầu vào:

• Dòng 1: hai số nguyên dương ~N~ và ~K~ ~(K \leq N \leq 10^5)~;
• Dòng 2: gồm ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ ~(a_i \leq 10^9)~.

Đầu ra:

• In ra đáp án thỏa mãn yêu cầu đề bài.

Ví dụ:

                INPUT                           OUTPUT

                6 2                             11
                2 4 5 2 9 1

Trong một kỳ thi, việc sáng tạo bài dễ nhất trong đề thi nhiều khi cũng mất không ít thời gian. Trong đề thi Duyên Hải năm 2021, Ban giám khảo muốn tạo một bài dễ thao tác trên dãy số cho các học sinh khối 10. Bài toán dưới đây đã được sáng tạo và chọn vào đề thi, bài toán này có thể giải được bằng nhiều thuật toán khác nhau.

Cho dãy số nguyên ~a_1, a_2, ..., a_n~, một đoạn ~a_L, a_{L+1},..., a_R~ ~(1 \leq L \leq R \leq N)~ được gọi là đoạn đẹp nếu ~L, R~ đều là số nguyên tố. Hãy tìm đoạn đẹp có tổng lớn nhất.

Input

Vào từ thiết bị vào chuẩn theo khuôn dạng:

• Dòng đầu chứa số nguyên dương ~n~ ~(n \geq 2)~;
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(|a_i| \leq 10^6)~.

Output

• Ghi ra thiết bị ra chuẩn một số nguyên là tổng lớn nhất của đoạn đẹp tìm được.

Scoring

• Subtask ~1~ ~(40\%~ số điểm): ~n \leq 100~;
• Subtask ~2~ ~(30\%~ số điểm): ~n \leq 3000~;
• Subtask ~3~ ~(30\%~ số điểm): ~n \leq 10^6~.

Ví dụ:

                    INPUT                       OUTPUT

                    6                           8
                    9 5 -2 6 -1 1                    

Bạn có 2 mảng số nguyên không âm được sắp xếp theo thứ tự không giảm a gồm n phần tử và b gồm m phần tử.

Hãy ghép a và b thành một mảng số nguyên c gồm n + m phần tử.

Hãy cho biết mảng c theo thứ tự không giảm.

Constants:

• 1 ≤ n, m ≤ 10^5
• 0 ≤ a_i, b_i ≤ 10~^9~

Ví dụ:

Input                           Output
6 7                             1 2 3 6 8 9 13 13 15 18 18 21 25
1 6 9 13 18 18
2 3 8 13 15 21 25