Lưu ý : Bài này khác phiên bản khó chỉ ở cấu trúc dữ liệu và giá trị ai.
Ami có một dãy số A độ dài n và được đánh số từ 1. Số được đánh số là i có giá trị là ai. Cần đếm xem có bao nhiêu số D ≥ 0 mà tồn tại một dãy con liên tiếp của A là một cấp số cộng có công sai D. Với mỗi số D, hãy tìm dãy con liên tiếp của dãy A dài nhất và là một cấp số cộng có công sai là D.
Input
Dòng đầu tiên là một số n (n ≤ 3*105) là độ dài dãy A.
Dòng tiếp theo là n số nguyên dương a1, a2, a3, ..., an (ai ≤ 102) là các phần tử của dãy A
Output
Gồm một số dòng, mỗi dòng có dạng D x, ý nghĩa là có một dãy con liên tiếp của A có độ dài x và là một cấp số cộng là D. x là lớn nhất trong các dãy con liên tiếp của A thoả mãn điều kiện này.
Các bạn cần in đáp án theo thứ tự tăng dần của D
Giải thích
Ta có dãy số là 3 2 1 0 1 2 4 6 8.
Một dãy con có cấp số cộng là 1 : |0 1 2| có độ dài là 3.
Một dãy con có cấp số cộng là 2 : |2 4 6 8| có độ dài là 4.
Có dãy con có cấp số cộng là -1 : |3 2 1 0|. Tuy nhiên ta chỉ quan tâm đến các dãy có công bội D ≥ 0.