Nhà Thám Hiểm

Trước khi bắt đầu chuyến thám hiểm hang động bí ẩn, nhà thám hiểm Cin cần chuẩn bị lương thực cho hành trình. Có \(N\) chiếc rương được xếp thành một hàng, chiếc rương thứ \(i\) chứa \(a_i\) phần lương thực.

Do sức chứa của ba lô có hạn, Cin chỉ có thể chọn hai chiếc rương đứng cạnh nhau để mang theo.

Yêu cầu: Hãy giúp Cin tìm hai chiếc rương chứa tổng lượng lương thực lớn nhất để chuẩn bị tốt nhất cho chuyến thám hiểm.

Input

• Dòng đầu tiên chứa số nguyên \(N\) (\(2 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \ldots, a_N\) (\(1 \le a_i \le 10^9\)) tương ứng với lượng vàng trong mỗi chiếc rương.

Output

• In ra một số nguyên duy nhất là lượng lương thực lớn nhất của hai chiếc rương đứng cạnh nhau.

Example

4
1 3 2 4

6

Sau nhiều ngày vượt qua sa mạc và những cánh rừng bí ẩn, cuối cùng Cin cũng tìm thấy kho báu ẩn sâu trong một hang động cổ. Trước mắt Cin là \(N\) chiếc rương lớn nhỏ chứa đầy vàng, được xếp thành một hàng dài. Chiếc rương thứ \(i\) chứa \(a_i\) đồng vàng.

Nhưng kho báu được bảo vệ bởi một lời nguyền cổ xưa: nếu mở hai chiếc rương nằm cạnh nhau, toàn bộ số vàng trong hang sẽ biến mất!

Để mang về nhiều vàng nhất có thể mà không phá vỡ lời nguyền, nhà thám hiểm cần lựa chọn những chiếc rương một cách cẩn thận sao cho không có hai chiếc rương nào được chọn nằm cạnh nhau.

Yêu cầu: Tính tổng số vàng lớn nhất mà nhà thám hiểm Cin có thể thu thập.

Input

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \leq N \leq 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(0 \leq a_i \leq 10^9\)) là số lượng đồng vàng trong mỗi chiếc rương.

Output

• In ra một số nguyên duy nhất là tổng số vàng lớn nhất có thể lấy được.

Example

5
3 2 7 10 9

19

Sau hành trình dài khám phá một hang động bí ẩn, Cin đã tìm thấy lối ra. Thế nhưng, ngay trước mắt Cin là một cánh cổng đá khổng lồ, ngăn cách với thế giới bên ngoài. Cánh cổng đã bị phong ấn từ hàng nghìn năm trước và chỉ có thể mở bằng một chiếc chìa khóa đặc biệt.

Theo những dòng chữ cổ khắc trên vách đá, chiếc chìa khóa này được ghép từ hai mảnh chìa khóa nằm trong hai chiếc rương khác nhau. Trong hang động có \(N\) chiếc rương được xếp thành một hàng, chiếc rương thứ \(i\) chứa một mảnh chìa khóa mang số hiệu \(a_i\). Hai mảnh chìa khóa chỉ có thể ghép thành chìa khóa hoàn chỉnh khi tổng số hiệu của chúng bằng đúng \(K\).

Thời gian không còn nhiều, Cin phải nhanh chóng tìm ra những cặp rương phù hợp để ghép thành một chiếc chìa khóa hoàn chỉnh, mở ra cánh cổng và trở về nhà trước khi Cin bị cạn kiệt lương thực và nước uống.

Yêu cầu: Hãy viết chương trình đếm số cách chọn hai chiếc rương khác nhau sao cho tổng số hiệu của hai mảnh chìa khóa bằng đúng \(K\).

Lưu ý: Hai cách chọn được xem là giống nhau nếu chúng chọn cùng hai chiếc rương, bất kể thứ tự lựa chọn.

Input

• Dòng đầu tiên gồm hai số nguyên \(N\) và \(K\) (\(1 \le N \le 10^5\), \(1 \le K \le 10^9\)).
• Dòng thứ hai gồm \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).

Output

• In ra một số nguyên duy nhất là số cách chọn hai chiếc rương thỏa mãn yêu cầu đề bài.

Example

4 5
1 2 3 4

2

Sau chuyến thám hiểm dài ngày, Cin mang về rất nhiều báu vật quý giá. Để chuẩn bị kinh phí cho chuyến phiêu lưu tiếp theo, Cin quyết định bán đi một số báu vật và giữ lại những món đồ có giá trị cao.

Cin có \(N\) báu vật được đánh số từ \(1\) đến \(N\), báu vật thứ \(i\) có giá trị \(a_i\). Cin chỉ bán những báu vật có giá trị nhỏ hơn \(100\) $, còn những báu vật có giá trị từ \(100\) $ trở lên sẽ được giữ lại làm kỷ niệm.

Nếu không có báu vật nào có giá trị nhỏ hơn \(100\) $, Cin sẽ bán báu vật có giá trị nhỏ nhất để có kinh phí cho chuyến đi.

Yêu cầu: Hãy viết chương trình xác định:

• Số lượng báu vật Cin bán được.
• Tổng số tiền thu được từ việc bán các báu vật đó.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(1 \le N \le 100\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) tương ứng với giá trị của các báu vật (\(1 \le a_i \le 1000\)).

Output

• Dòng đầu tiên in ra số lượng báu vật Cin bán được.
• Dòng thứ hai in ra tổng số tiền thu được từ việc bán các báu vật đó.

Example

5
50 120 80 99 150

3
229