Pracsiu Dan (dnprx) Se dă un șir A cu N elemente, numere naturale nenule, și un număr natural K. O subsecvență a șirului este un șir format din unul sau mai multe elemente aflate pe poziții consecutive în șirul inițial. Spunem că o valoare x se numește element majoritar al unei secvențe de lungime m, dacă ea apare în aceasta de cel puțin \( \left[ \frac{m}{2} \right] + 1\) ori.
Cerința
Să se afișeze valorile care sunt elemente majoritare pentru cel puțin o subsecvență de lungime mai mare sau egală cu K a șirului A.
Date de intrare
Pe prima linie a fișierului kmajo.in se află numerele naturale N și K, cu semnificația din enunț, iar pe a doua linie se găsesc N numere naturale, reprezentând elementele șirului A. Valorile aflate pe aceeași linie sunt separate prin câte un spațiu.
Date de ieșire
Fișierul de ieșire kmajo.out va conține pe prima linie valorile cerute, în ordine strict crescătoare, separate prin câte un spațiu, sau valoarea -1, dacă nu există cel puțin o valoare care să respecte restricțiile impuse.
Restricții și precizări
1 ≤ K ≤ N ≤ 1.000.000.1 ≤ A[i] ≤ N, pentru oricei = 1, 2, ..., n.- Pentru 11 puncte,
K = N - Pentru 16 puncte,
N ≤ 1000 - Pentru 22 de puncte,
N * K ≤ 30.000.000 - Pentru 30 de puncte,
N ≤ 100.000 - Pentru 21 de puncte, nu există alte restricții
Exemplu:
kmajo.in
12 3 2 2 1 3 4 2 2 3 3 3 4 4
kmajo.out
2 3 4
Explicație
2 este element majoritar în mai multe subsecvențe de lungime mai mare sau egală cu 3, un exemplu fiind:
2 2 1 3 4 2 2 3 3 3 4 4
3 este element majoritar în mai multe subsecvențe de lungime mai mare sau egală cu 3, un exemplu fiind:
2 2 1 3 4 2 2 3 3 3 4 4
4 este element majoritar în următoarea subsecvență evidențiată, de lungime mai mare sau egală cu 3.
2 2 1 3 4 2 2 3 3 3 4 4