Cho một chuỗi ký tự chỉ gồm 2 loại dấu ngoặc: '(' và ')'. Bạn hãy tìm độ dài của chuỗi con liên tiếp hợp lệ (các ngoặc đóng mở đúng quy tắc) dài nhất trong chuỗi đã cho.

Input: Một chuỗi ký tự (Độ dài <= 10^5).

Output: Độ dài chuỗi con hợp lệ lớn nhất.

Ví dụ:

Input:

)((()())(

Output:

6

(Giải thích: Chuỗi con hợp lệ dài nhất là "(()())" ở giữa).

Bạn biết trước giá cổ phiếu của một công ty trong N ngày tới, giá ngày thứ i là P_i. Bạn được phép mua và bán nhiều lần để kiếm lời, nhưng phải tuân thủ luật: Bạn không thể nắm giữ quá 1 cổ phiếu tại cùng 1 thời điểm; và sau khi bán cổ phiếu, bạn bắt buộc phải nghỉ ngơi 1 ngày (không được mua vào ngày hôm sau, gọi là ngày đóng băng - cooldown). Tính lợi nhuận lớn nhất bạn có thể thu được.

Input:

Dòng 1: N (1 <= N <= 10^5).

Dòng 2: N số nguyên Pi (0 <= Pi <= 10^4).

Output: Lợi nhuận cực đại.

Ví dụ:

Input:

5
1 2 3 0 2

Output:

3

Một hàng rào được ghép từ N tấm ván hình chữ nhật xếp sát nhau. Tấm ván thứ i có chiều rộng là 1 và chiều cao là H_i. Hội học sinh muốn dán một tấm áp phích hình chữ nhật lớn nhất có thể lên hàng rào này (tấm áp phích phải đặt thẳng đứng và không được thò ra ngoài hàng rào). Hãy tìm diện tích lớn nhất của tấm áp phích đó.

Input:

Dòng 1: N (1 <= N <= 10^5).

Dòng 2: N số nguyên Hi (1 <= Hi <= 10^9).

Output: Diện tích áp phích lớn nhất.

Ví dụ:

Input:

6
2 1 5 6 2 3

Output:

10

(Giải thích: Dán áp phích từ tấm ván 3 đến 4 (cao 5 và 6). Lấy chiều cao chung là 5, chiều rộng là 2. Diện tích = 5 * 2 = 10).

Gần đây Polycarp nhận thấy rằng một số nút trên bàn phím của anh ta bị trục trặc. Để đơn giản, chúng tôi giả định rằng bàn phím của Polycarp chứa 26 nút (một nút cho mỗi chữ cái trong bảng chữ cái Latinh). Mỗi nút đều hoạt động tốt hoặc trục trặc. Để kiểm tra các nút nào cần thay thế, Polycarp nhấn một số nút theo trình tự và một chuỗi s xuất hiện trên màn hình. Khi Polycarp nhấn nút có ký tự c, một trong những sự kiện sau đã xảy ra: nếu nút hoạt động chính xác, một ký tự c xuất hiện ở cuối chuỗi Polycarp đang gõ; nếu nút bị trục trặc, hai ký tự c xuất hiện ở cuối chuỗi.

Ví dụ: giả sử các nút tương ứng với các ký tự a và c hoạt động chính xác và nút tương ứng với b bị trục trặc. Nếu Polycarp nhấn các nút theo thứ tự a, b, a, c, a, b, a, thì chuỗi anh ta đang gõ thay đổi như sau: a → abb → abba → abbac → abbaca → abbacabb → abbacabba. Bạn được cung cấp một chuỗi s xuất hiện trên màn hình sau khi Polycarp nhấn một số nút. Giúp Polycarp xác định nút nào đang hoạt động chính xác (chắc chắn, chuỗi này không thể xuất hiện trên màn hình nếu bất kỳ nút nào trong số này bị trục trặc). Bạn có thể cho rằng các nút không bắt đầu gặp trục trặc khi Polycarp gõ chuỗi: mỗi nút hoạt động chính xác trong toàn bộ quá trình hoặc trục trặc trong toàn bộ quá trình.

Đầu vào:

• Dòng đầu tiên chứa một số nguyên t (1≤t≤100) - số lượng trường hợp kiểm tra trong đầu vào.
• Sau đó các trường hợp kiểm tra làm theo. Mỗi trường hợp kiểm tra được đại diện bởi một dòng chứa một chuỗi s bao gồm không ít hơn 1 và không quá 500 chữ cái Latinh viết thường.

Đầu ra: Đối với mỗi trường hợp thử nghiệm, in một dòng có chứa độ phân giải chuỗi. chuỗi phải chứa tất cả các ký tự tương ứng với các nút hoạt động chính xác theo thứ tự bảng chữ cái, không có bất kỳ dấu cách hoặc lặp lại. Nếu tất cả các nút có thể gặp trục trặc, độ phân giải sẽ trống.

Input:

4
a
zzaaz
ccff
cbddbb

Output:

a
z

bc

Bạn được cung cấp một chuỗi s bao gồm n chữ cái viết thường, n là chẵn. Đối với mỗi vị trí i (1≤i≤n) trong chuỗi s, bạn được yêu cầu thay đổi chữ cái trên vị trí này thành chữ cái đứng trước theo thứ tự chữ cái hoặc sang vị trí tiếp theo (chữ 'a' và 'z' chỉ có một những lựa chọn này). Mọi vị trí trong chuỗi phải được thay đổi chính xác một lần. Ví dụ: có thể thay đổi chữ 'p' thành 'o' hoặc thành 'q', chữ 'a' nên được đổi thành 'b' và chữ 'z' được đổi thành 'y' mà không thể đổi thành 'a'. Ví dụ, chuỗi "codeforces" có thể được thay đổi thành "dpedepqbft" ('c' → 'd', 'o' → 'p', 'd' → 'e', 'e' → 'd', 'f' → 'e', 'o' → 'p', 'r' → 'q', 'c' → 'b', 'e' → 'f', 's' → 't'). Chuỗi s được gọi là palindrom nếu nó đọc tương tự từ trái sang phải và từ phải sang trái. Ví dụ: chuỗi "abba" và "zz" là palindromes và chuỗi "abca" và "zy" thì không. Mục tiêu của bạn là kiểm tra xem có thể biến chuỗi s thành một chuỗi palindrome hay không bằng cách áp dụng các thay đổi đã nói ở trên cho mọi vị trí. In "YES" nếu chuỗi s có thể được chuyển thành bảng màu và "NO" nếu không. Mỗi testcase chứa một số chuỗi, đối với mỗi chuỗi, bạn được yêu cầu giải quyết vấn đề một cách riêng biệt.

Đầu vào:

• Dòng đầu tiên chứa một số nguyên T (1≤T≤50) - số testcase.
• Sau đó, các dòng 2T theo sau . Dòng đầu tiên của testcase chứa một số nguyên n (2≤n≤100, n là chẵn) - độ dài của chuỗi tương ứng. Dòng thứ hai của testcase chứa một chuỗi s, bao gồm n chữ cái Latinh viết thường.

Đầu ra: In dòng T. Dòng thứ i nên chứa câu trả lời cho chuỗi thứ i của đầu vào. In "YES" nếu có thể biến chuỗi thứ i thành chuỗi palindrome bằng cách áp dụng các thay đổi đã nói ở trên cho mọi vị trí. In "NO" nếu không.

Input:

5
6
abccba
2
cf
4
adfa
8
abaazaba
2
ml

Output:

YES
NO
YES
NO
NO

Ghi nhận sự biến động nhiệt độ trong N ngày là một mảng các số nguyên (âm, dương, hoặc bằng 0). Một chu kỳ liên tiếp các ngày được coi là "ổn định" nếu tổng các biến động trong chu kỳ đó bằng đúng 0. Bạn hãy tìm ra chu kỳ ổn định có thời gian kéo dài (số ngày) lâu nhất.

Input:

Dòng 1: N (1 <= N <= 10^5).

Dòng 2: N số nguyên Ai (|Ai| <= 10^4).

Output: Số ngày của chu kỳ ổn định dài nhất. Nếu không có, in 0.

Ví dụ:

Input:

6
1 -1 2 -2 3 -3

Output:

6

Hai số nguyên dương được coi là một "cặp đôi hoàn hảo" nếu cả hai đều là số nguyên tố và chúng có tổng các chữ số bằng nhau. Cho một mảng gồm N số nguyên dương phân biệt, hãy đếm xem trong mảng này có bao nhiêu cặp đôi hoàn hảo (không phân biệt thứ tự cặp).

Input:

Dòng 1: N (1 <= N <= 10^5).

Dòng 2: N số nguyên dương Ai (1 <= Ai <= 10^6).

Output: Số lượng cặp đôi hoàn hảo.

Ví dụ:

Input:

5
11 2 23 5 41

Output:

4