C. Геометр прогресс

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$3$ настай Поликарп $3$ гишүүнтэй геометр прогресст маш их дуртай. Түүнд одоогоор $n$ бүхэл тооноос бүрдсэн $a$ дараалал, мөн бүхэл тоо $k$ байгаа.

Тэрээр хичнээн ширхэг $k$ ноогдвортой $3$ гишүүнтэй урттай геометр прогрессыг $a$ дарааллаас сонгон авч болохыг мэдэхийг хүсэв.

Сонгон авах $3$ урттай дэд дараалал нь $1 ≤ i_{1} < i_{2} < i_{3} ≤ n$ байх $3$ ширхэг $i_{1}, i_{2}, i_{3}$ дугаараар илэрхийлэгдэх ба эдгээр дугаарууд нь $a$ дараалал доторх дараалсан элементүүдийн дугаар байх шаардлагагүй бөгөөд эдгээр дугаарууд нь заавал өсөх эрэмбээр байрласан байх ёстой юм.

$k$ ноогдвортой геометр прогресс гэдэг нь $b \cdot k^{0}, b \cdot k^{1}, ..., b \cdot k^{r - 1}$ хэлбэр бүхий тоон дарааллыг хэлнэ.

Поликарп дөнгөж гуравхан настай учраас үүнийг тооцоолж чадахгүй байгаа юм. Иймээс түүнд үүнийг хийхэд тусална уу.

Оролт

Эхний мөрөнд Поликарпын дарааллын урт болох $n$ ба түүний дуртай тоо болох $k$ бүхэл тоонууд өгөгдөнө. ($1 ≤ n, k ≤ 2 \cdot 10^{5}$)

Дараагийн мөрөнд Поликарпын дарааллын гишүүд болох $n$ ширхэг бүхэл тоо $a_{1}, a_{2}, ..., a_{n}$ ($-10^{9} ≤ a_{i} ≤ 10^{9}$) өгөгдөнө.

Гаралт

$k$ ноогдвортой геометр прогресс болж чадах $3$ урттай дэд дарааллын нийт тоог хэвлэнэ.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
5 2
1 1 2 2 4
Гаралт
4
Оролт
3 1
1 1 1
Гаралт
1
Оролт
10 3
1 2 6 2 3 6 9 18 3 9
Гаралт
6

Тэмдэглэл

Эхний жишээнд $2$ ширхэг $1$ гэсэн гишүүдийн аль нь ч дэд дарааллын эхний гишүүн болж чадах ба $2$ дахь гишүүн нь мөн л адил $2$ ширхэг $2$ гэсэн гишүүдийн аль нь ч байж болно. $3$ дахь гишүүн нь заавал $4$ байна. Иймээс энэ жишээний хариу $4$ байна.

Сэтгэгдлүүдийг ачааллаж байна...