Cho dãy số ~A~ gồm ~n~ số nguyên dương ~A_1, A_2, \dots, A_n~. Một bộ ba số được gọi là bộ số tam giác, nếu ba số này là độ dài ba cạnh của một tam giác.

Yêu cầu: Hãy đếm xem trong dãy ~A~ có bao nhiêu bộ số tam giác ~(A_i, A_j, A_k)~ với ~i, j, k~ đôi một khác nhau.

Input:

Vào từ file văn bản BSTG.INP gồm:

• Dòng đầu chứa số nguyên ~n\ (3 ≤ n ≤ 1000)~.
• Dòng tiếp theo chứa ~n~ số nguyên dương trong dãy ~A\ (A_i ≤ 10^9)~.

Output:

• Ghi ra file văn bản BSTG.OUT số lượng bộ số tam giác trong dãy đã cho.

Ví dụ:

BSTG.INP

5
4 3 1 5 7

BSTG.OUT

3

Giải thích

Có ~3~ bộ số tam giác là ~(4, 3, 5),\ (4, 5, 7)~ và ~(3, 5, 7)~.

Subtask:

• ~60\%~ số test có ~n \le 500~.
• ~40\%~ số test không có ràng buộc gì thêm.

Dạo một vòng Facebook, Loli cảm thấy rất chán khi thấy giới trẻ cứ thấy cái gì đấy là lại muốn "uoc j uoc j". Vì vậy Loli nhờ các bạn coder giải quyết vấn nạn nhức nhối này bằng việc tạo ra chương trình trả lời hết các câu "uoc j".

Input:

• Dòng đầu tiên chứa một số nguyên ~j~ ~(1 \le j \le 10^{12})~.

Output:

• Gồm một dãy số nguyên tăng dần là ước của ~j~.

Sample Input 1

3

Sample Output 1

1 3

Sample Input 2

69

Sample Output 2

1 3 23 69

Nhà cung cấp dịch vụ viễn thông Mobi đã khảo sát số lượng người sẽ dùng dịch vụ trên một con đường thẳng mới được xây dựng và đánh dấu lại những vị trí trên con đường này. Đầu con đường được đánh tọa độ bắt đầu từ ~0~. Tại vị trí có tọa độ ~X~ (~X~ nguyên dương) có số lượng người sẽ sử dụng dịch vụ là ~Y~. Trước mắt, nhà cung cấp dịch vụ cần đặt một trạm phát sóng có bán kính phủ sóng là ~K~ đơn vị chiều dài để phủ sóng cho một số người sử dụng dịch vụ trên con đường này.

Yêu cầu: Bạn hãy xác định vị trí đặt trạm phát sóng (tọa độ nguyên dương) sao cho trạm có thể phục vụ được số lượng người sử dụng nhiều nhất có thể.

Input:

Vào từ file văn bản "MOBI.INP":

• Dòng đầu tiên ghi hai số nguyên ~N~ và ~K~ ~(0 < N \le 10^6,\ 0 < K \le 2 \times 10^6)~, trong đó ~N~ là số điểm dân cư đã được đánh dấu, ~K~ là bán kính phủ sóng của trạm.
• Trong ~N~ dòng tiếp theo, dòng thứ ~i\ (i=1..N)~ ghi hai số nguyên ~X~ và ~Y~ cho biết tại vị trí ~X~ có số lượng người dùng là ~Y (0 \le X \le 10^6,\ 0 \le Y \le 10^4)~. Các số trên cùng dòng viết cách nhau ít nhất một dấu cách.

Output:

Ghi ra file văn bản "MOBI.OUT" một số nguyên cho biết số người dùng nhiều nhất sẽ được phục vụ.

Sample Input 1

4 3
7 4
15 10
2 2
1 5

Sample Output 1

11

Cửa hàng sách 210VN dạo gần đây đang vắng khách một cách lạ kỳ. Sau khi tìm hiểu vài khóa tăng sale, họ đã tâm đắc với chiến dịch kích cầu nổi tiếng: "mua ~x~ trả tiền ~x-1~". Ưu đãi rất có lợi dành cho các bạn fan cứng của nhiều thể loại sách, đặc biệt là thể loại truyện segg. Ưu đãi vô cùng đơn giản: Khi mua ~x~ cuốn truyện segg sướt mướt, khách hàng sẽ được miễn phí cuốn rẻ nhất trong ~x~ cuốn này. Ví dụ, với ~x=3~, khi mua hai cuốn truyện đình đám 177013 và 161531, khách hàng được tặng miễn phí cuốn 228922 đầy căng cực.

Hơn nữa, nếu khách hàng muốn mua nhiều hơn ~x~ cuốn, họ có thể chia số sách muốn mua thành các nhóm, mỗi nhóm gồm từ ~1~ tới ~x~ cuốn. Trong mỗi nhóm ~x~ cuốn, khách hàng sẽ được tặng cuốn có giá thấp nhất trong ~x~ cuốn này. Các nhóm có số lượng sách nhỏ hơn ~x~ không được hưởng ưu đãi.

Vốn là fan cứng yêu thích các tác phẩm sến súa ướt át, Loli ngây thơ muốn mua ~n~ cuốn truyện segg với giá ~c_1,c_2,\ldots,c_n~. Hãy tìm cách để mua ~n~ cuốn này với giá thấp nhất dựa trên ưu đãi "mua ~x~ trả tiền ~x-1~" của cửa hàng.

Input:

Lấy từ tệp DISCOUNT.INP gồm:

• Dòng đầu tiên chứa số nguyên ~n,x\ (2\le n,x\le10^5)~ là số sách muốn mua và ưu đãi của cửa hàng.
• Dòng 2 chứa ~n~ số nguyên ~c_i\ (1 \le c_i \le 9696969)~ là giá tiền của cuốn sách thứ ~i~.

Output:

• Ghi ra tệp DISCOUNT.OUT là tổng số tiền nhỏ nhất cần phải trả.

Sample Input 1

4 3
3 2 3 2

Sample Output 1

8

Sample Input 2

6 3
6 4 5 5 5 5

Sample Output 2

21

Giải thích

Ở test đầu, mua 3 cuốn có giá là ~3,\ 2,\ 3~, ta được free cuốn ~2~ đồng. Sau đó mua cuốn còn lại.

Ràng buộc

• 50% số test có ~n\le5000~.
• 50% số test còn lại không có ràng buộc gì thêm.

Trong đợt bùng phát dịch COVID-19 đầu tiên, xét nghiệm trên diện rộng với từng người là một trong những chiến lược tốt để kiểm soát và ngăn chặn dịch lây lan mạnh. Tuy nhiên, xét nghiệm bằng PCR tiêu tốn khá nhiều thời gian và tiền bạc. Một cách làm hiệu quả để tăng tốc quá trình và tiết kiệm tài nguyên vốn đã hạn hẹp là thực hiện xét nghiệm theo từng hộ gia đình. Với cách làm này, thay vì xét nghiệm từng người, ta hợp mẫu thử của p người và xét nghiệm trong một lần. Nếu cho ra kết quả 1 vạch, chúng ta có thể kết luận rằng cả p người đều âm tính. Ngược lại, nếu chẳng may kết quả có thêm vạch nữa, chúng ta lại phải xét nghiệm riêng từng người để xem ai là người bị nhiễm virus.

Trong một khu vực có ~n~ hộ gia đình, mỗi hộ được đánh số từ ~0~ đến ~n-1~. Hộ thứ ~i~ có ~a_i~ thành viên. Sau khi làm ~n~ xét nghiệm cho ~n~ hộ, ta có ~k~ hộ có kết quả dương tính. Nhiệm vụ của bạn là tính số lần xét nghiệm riêng lẻ tối đa và tối thiểu mà nhân viên y tế phải làm.

Input:

• Dòng đầu tiên chứa số nguyên ~n\ (1 \le n \le 10^5)~ và ~k\ (k \le n)~ với ý nghĩa như trên.
• Dòng tiếp theo chứa ~n~ số nguyên ~p_i\ (1 \le p_i \le 10^4)~ là số ngưởi trong hộ thứ ~i~.

Output:

• Gồm 2 số nguyên dương là số lần xét nghiệm thêm tối thiểu và tối đa.

Sample Input 1

5 2
2 3 6 4 5

Sample Output 1

5 11

Sample Input 2

3 1
1 2 3

Sample Output 2

0 3

Giải thích

• Ở testcase 1: Nếu hộ thứ ~0~ và ~1~ dương tính thì ta chỉ cần làm ~5~ lần xét nghiệm riêng. Nếu hộ thứ ~2~ và ~4~ dương tính thì ta cần làm ~11~ lần xét nghiệm riêng. ~5~ lần là ít nhất, ~11~ lần là nhiều nhất.
• Ở testcase 2: Nếu hộ thứ ~0~ dương tính thì ta không cần xét nghiệm thêm vì hộ này chỉ có ~1~ người. Nếu hộ thứ ~2~ dương tính thì ta cần làm ~3~ lần xét nghiệm nữa.

Loli đang triển khai một đội hình đặc nhiệm để chuẩn bị cho kế hoạch tiếp theo. Trong lúc kiểm tra lại đội hình một lần cuối, Loli nhận ra có gì đó sai sai. Trong đội hình toàn đặc nhiệm cao đều răm rắp, có một chỗ lại bị thò thụt bất thường, và chỉ có một chỗ bị như vậy.

Loli báo cáo lại cho cấp dưới. Cấp dưới không tin có chuyện đó xảy ra. Tuy nhiên, với cách suy nghĩ "Đúng nhận sai cãi", cấp dưới truyền lệnh cho đội hình đặc nhiệm dàn ra thành một hàng ngang, đánh số từng người lần lượt từ ~1~ đến ~n~, sau đó sử dụng một máy đo chuyên dụng để biết độ cao của từng người.

Công việc còn lại của Loli là code chương trình để tìm ra được kẻ giả mạo đó. Nhưng Loli lười code nên giao trọng trách lại cho bạn. Bạn hãy xác định xem Cấp dưới sẽ phải nhận hay được cãi. Nếu đúng có kẻ giả mạo, hãy cho biết số thứ tự của kẻ đó.

Input:

Lấy từ tệp IMPOSTOR.INP gồm:

• Dòng đầu tiên chứa một số nguyên dương ~n~ ~(3\le n\le 10^5)~ là số người.
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_i~ ~(1\le a_i \le 10^9)~ là chiều cao của đặc nhiệm có số thứ tự ~i~.

Output:

Ghi ra tệp IMPOSTOR.OUT gồm:

• Dòng thứ nhất ghi kết quả cuộc điều tra. Nếu tất cả đều có chiều cao bình thường, in ra YES, ngược lại, in ra NO.
• Dòng thứ hai ghi một số nguyên là số thứ tự của kẻ giả mạo, nếu có. Nếu không có kẻ giả mạo nào, in ra ~-1~ ở dòng này.

Sample Input 1

4
11 11 13 11

Sample Output 1

NO
3