Bài tập

Cho một dãy số gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^6, 1 \leq i \leq n \leq 10^6\)).

**Yêu cầu:** Tìm dãy con có tổng các phần tử là lớn nhất trong các dãy con không giảm, nếu có nhiều dãy con thoả mãn thì in ra các dãy con theo thứ tự xuất hiện.

Input

Vào từ file SUBSEQ.INP gồm:

• Dòng đầu: số nguyên dương \(n\);
• Dòng tiếp theo: \(n\) số nguyên dương cách nhau khoảng trắng.

Output

Ghi ra file SUBSEQ.OUT gồm:

• Dòng đầu: tổng lớn nhất tìm được;
• Các dòng tiếp theo: các dãy con thỏa mãn.

Example

10
2 2 3 4 6 6 7 7 8 8

53
2 2 3 4 6 6 7 7 8 8 

11
4 7 4 5 7 4 9 3 3 4 6

16
4 5 7 
3 3 4 6 

Scoring

Ràng buộc:

• Có 20% số điểm ứng với \(n = 10\) và dãy không giảm;
• Có 20% số điểm ứng với \((11 \leq n \leq 200)\);
• Có 20% số điểm ứng với \((201 \leq n \leq 10^3)\);
• 40% số điểm còn lại ứng với \((10^3 < n \leq 10^6)\).

Cho một mảng \(a\) gồm \(n\) phần tử \(a_1, a_2, \dots, a_n\).

Mảng bộ ba được định nghĩa gồm các \(\min(a_i, a_j, a_k)\) với tất cả các bộ ba \((i, j, k)\) thỏa mãn \(1 \le i < j < k \le n\), trong đó \(\min(a_i, a_j, a_k)\) là giá trị nhỏ nhất của 3 phần tử \(a_i, a_j, a_k\).

Cho \(q\) truy vấn thuộc loại sau: "Cho số nguyên \(k\), trả lại phần tử nhỏ thứ \(k\) trong mảng bộ ba".

Input

Vào từ tệp văn bản trip.inp:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((3 \le n \le 3 \times 10^5; 1 \le q \le 3 \times 10^5)\) tương ứng là số phần tử mảng \(a\) và số truy vấn;
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((-10^9 \le a_i \le 10^9)\);
• Mỗi dòng trong \(q\) dòng tiếp theo chứa một số nguyên \(k\) \((1 \le k \le \frac{n(n-1)(n-2)}{6})\) mô tả một truy vấn.

Output

Ghi ra tệp văn bản trip.out. Với mỗi truy vấn, in ra trên một dòng phần tử nhỏ thứ \(k\) trong mảng bộ ba.

Example

4 4
2 4 2 1
1
2
3
4

1
1
1
2

Scoring

• 40% số test: \(3 \le n \le 10^2\);
• 40% số test: \(3 \le n \le 10^3\) và \(1 \le q \le 10^4\);
• 20% số test: Không có thêm ràng buộc nào.

Cho dãy số nguyên dương \(A = (a_1, a_2, ..., a_n)\).

Hãy đếm xem có bao nhiêu cặp số bằng nhau trong dãy \(A\).

Input

**Dữ liệu vào: ** Dữ liệu vào từ tệp văn bản CSBN.INP có cấu trúc:

• Dòng đầu tiên ghi số nguyên dương \(n (n \leq 10^6)\).
• Dòng thứ hai ghi \(n\) số nguyên dương \(a_1, a_2, ..., a_n (a_i \leq 10^9, i = 1, 2, 3, ..., n)\), các số được ghi cách nhau một dấu cách trống.

Output

**Dữ liệu ra: ** Ghi vào tệp văn bản CSBN.OUT ghi duy nhất một số là kết quả tìm được

Example

5
10 9 6 5 9

1

6
10 11 12 11 11 15

3

Scoring

• Có \(40\%\) số test tương ứng với \(40\%\) số điểm của bài có \(n \leq 10^3\).
• Có \(60\%\) số test tương ứng với \(60\%\) số điểm của bài có \(n > 10^3\) và \(a_i \leq 10^6\).

Bạn được cung cấp một bức ảnh có kích thước \(n \times m\) điểm ảnh. Mỗi điểm ảnh là màu trắng hoặc đen.

Nhiệm vụ của bạn là thay đổi càng ít điểm ảnh càng tốt để bức ảnh trở thành một mã vạch hợp lệ.

Một bức ảnh được xem là mã vạch nếu thỏa mãn hai điều kiện sau:

• Mỗi cột chỉ có một màu duy nhất (hoặc toàn trắng, hoặc toàn đen).
• Khi nhóm các cột liền kề có cùng màu lại, kích thước của mỗi nhóm phải nằm trong đoạn \([x, y]\).

Mục tiêu: Tìm số điểm ảnh ít nhất cần tô lại để bức ảnh trở thành mã vạch hợp lệ.

\InputFile

• Dòng đầu tiên chứa bốn số nguyên \(n, m, x, y\) (\(1 \le n \times m \le 10^6, x \le y \le 10^6\)).
• Tiếp theo là \(n\) dòng, mỗi dòng gồm đúng \(m\) ký tự, mô tả bức ảnh ban đầu.
• Mỗi ký tự là '.' (điểm trắng) hoặc # (điểm đen).

\OutputFile

In ra một số nguyên duy nhất --- số điểm ảnh ít nhất cần tô lại. Đảm bảo rằng luôn tồn tại cách làm thỏa mãn yêu cầu.

\Scoring

• Subtask 1 (22 điểm): \(n \cdot m \le 20\)
• Subtask 2 (18 điểm): Tất cả các ô đều có màu trắng.
• Subtask 3 (30 điểm): \(m \le 1000\)
• Subtask 4 (30 điểm): Không có giới hạn gì thêm

Example

6 5 1 2
##.#.
.###.
###..
#...#
.##.#
###..

11

2 5 1 1
#####
.....

5