Bình mua bán cổ phiếu HCN trên thị trường chứng khoán. Giả sử giá của một cổ phiếu HCN trong vòng N ngày lần lượt là A1, A2,..., AN. Biết rằng mỗi ngày Bình chỉ thực hiện một trong những hoạt động sau:

1. Mua một cổ phiếu HCN;

2. Bán số lượng cổ phiếu HCN bất kì mà Bình đang sở hữu;

3. Không thực hiện bất kì giao dịch nào.

Yêu cầu: Bình thực hiện mua bán cổ phiếu HCN như thế nào để thu được lợi nhuận lớn nhất nếu anh ấy tham gia mua bán bắt đầu từ ngày thứ T cho trước?

Dữ liệu nhập vào:

• Dòng đầu tiên gồm số nguyên dương N (N ≤ 10^5) là số ngày biết giá cổ phiếu;

• Dòng thứ hai gồm N số nguyên dương A1, A2, ..., Av tương ứng là giá của một cổ phiếu VNI trong từng ngày (Ai ≤ 10^9; 1 ≤ i ≤ N);

• Dòng thứ ba gồm một số nguyên dương Q là số lượng truy vấn (Q ≤ 10^5);

Q dòng sau, mỗi dòng gồm một số nguyên dương T (T < N) thể hiện cho ngày đầu tiên mà Bình tham gia việc mua bán cổ phiếu HCN.

Kết quả ghi ra:

Q dòng, mỗi dòng gồm một số nguyên duy nhất là lợi nhuận lớn nhất mà Bình thu được ở mỗi truy vấn tương ứng.

Ràng buộc:

• Có 50% số test tương ứng với 50% số điểm thoa mãn: N ≤ 1000; Q = 1;

• 30% số test khác tương ứng với 30% số điểm thỏả mãn N ≤ 10^5; Q = 1;

• 20% số test còn lại tương ứng với 20% số điểm không có rằng buộc gì thêm.

Ví dụ:

Input:

4
1 2 5 4
2
1
3

Otuput:

7
0

Giải thích:

• Bình bắt đầu tham gia mua bán HCN vào ngày 1:

• Ngày 1: mua 1 HCN với giá là 1.

• Ngày 2: mua 1 HCN với giá là 2.

• Ngày 3: bán 2 HCN với giá là 5.

• Ngày 4: không mua hay bán HCN vào ngày này.

→ Lợi nhuận thu được là: - 1 - 2 + 2 × 5 = 7.

• Bình bắt đầu tham gia mua bán HCN vào ngày 3:

• Bình không mua bán HCN vào ngày 3 và ngày 4.

→ Lợi nhuận thu được là: 0.

Alice có một chuỗi s. Cô ấy thực sự thích chữ "a". Cô gọi một chuỗi là tốt nếu hơn một nửa số ký tự trong chuỗi đó là "a" s. Ví dụ: "aaabb", "axaa" là các chuỗi tốt và "baca", "awwwa", "" (chuỗi trống) thì không. Alice có thể xóa một số ký tự khỏi chuỗi s của mình. Cô ấy muốn biết chuỗi dài nhất còn lại là gì sau khi xóa một số ký tự (có thể bằng 0) để có được chuỗi được coi là tốt. Nó được đảm bảo rằng chuỗi có ít nhất một "a" trong đó, vì vậy câu trả lời luôn tồn tại.

Đầu vào: Nhập vào một chuỗi s (1≤ | s |<= 50) bao gồm các chữ cái tiếng Anh viết thường. Nó được đảm bảo rằng có ít nhất một "a" trong s.

Đầu ra: In một số nguyên duy nhất, độ dài của chuỗi tốt nhất dài nhất mà Alice có thể nhận được sau khi xóa một số ký tự khỏi s.

Input:

xaxxxxa

Output:

3

Hôm nay lại có n gian hàng bán đồ ăn tại lễ hội ở đền Hakurei. Yuyuko tham ăn có q lựa chọn dạng bi, ri, đi ăn tất cả cửa hàng ở vị trí bị đến vị trí ri.

Nhưng hôm nay do quá đói, cô đã đi ăn m lần, sử dụng tất cả các lựa chọn từ xi đến yi. Với mỗi gian hàng, hãy in ra số lần cô ghé thăm.

Đầu vào:

• Dòng đầu gồm 3 số tự nhiên n, g, m.

• g dòng tiếp theo mỗi dòng gồm 2 số 1 ≤ bi, ri ≤ n là lựa chọn thứ i.

• m dòng tiếp theo mỗi dòng gồm 2 số 1 ≤ xi, Yi ≤ q là lượt đi ăn thứ j.

Đầu ra:

• n số nguyên không âm là số lần cô ghé thăm các gian hàng.

Ràng buộc:

40% số điểm: n, q, m ≤ 100.

30% số điểm: n, q, m ≤ 5000.

30% số điểm: n, q, m ≤ 10^5

Input:

3 3 3
1 2
2 3
1 3
2 3
1 2
1 3

Output:

4 7 5

Keanu Reeves đang mắc kẹt trong thế giới ảo Ma Trận. Để chứng minh mình đang ở trong thế giới ảo, anh cần giải quyết một bài toán với chuỗi mật mã chỉ gồm các chữ số 0 và 1.

Trong thế giới này, một chuỗi mật mã được gọi là "Chuỗi An Toàn" nếu số lượng chữ số 0 và số lượng chữ số 1 trong chuỗi đó KHÁC NHAU. Ví dụ: Các chuỗi 1, 101, 0000 là an toàn. Các chuỗi 01, 1001, 111000 không an toàn (vì số lượng chữ số 0 bằng với số lượng chữ số 1).

Nhiệm vụ của bạn: Bạn được cấp một chuỗi mật mã S ban đầu. Bạn hãy cắt chuỗi S này thành ÍT ĐOẠN NHẤT có thể, sao cho TẤT CẢ các đoạn sau khi cắt đều là "Chuỗi An Toàn".

Lưu ý:

• Nếu chuỗi S ban đầu đã an toàn sẵn, bạn không cần cắt (tức là số đoạn cắt được k = 1).

• Nếu có nhiều cách cắt tạo ra số đoạn tối thiểu giống nhau, bạn có thể in ra bất kỳ cách nào.

Dữ liệu vào (Input):

• Dòng 1: Chứa một số nguyên N (1 <= N <= 100) là độ dài của chuỗi S.

• Dòng 2: Chứa chuỗi S có độ dài N (chỉ gồm các ký tự 0 và 1).

Dữ liệu ra (Output):

• Dòng 1: In ra số nguyên K là số lượng đoạn ít nhất mà bạn cắt được.

• Dòng 2: In ra K đoạn mật mã đó, mỗi đoạn cách nhau một khoảng trắng (dấu cách).

Ví dụ:

Input:

6 
100011

Output:

2 
100 011

Giải thích ví dụ: Chuỗi 100011 có 3 số '0' và 3 số '1' (không an toàn). Ta cắt thành 2 đoạn là 100 (có 2 số '0', 1 số '1') và 011 (có 1 số '0', 2 số '1'). Cả 2 đoạn này đều an toàn và đây là cách cắt tạo ra ít đoạn nhất.