Fiind dat un șir de numere, numim secvență a acestuia o parte dintre termenii șirului luați de pe poziții consecutive. Denumim platou al acestui șir o secvență formată din valori identice. Lungimea unui platou este egală cu numărul de elemente care îl formează.

De exemplu, în șirul de numere 1 1 1 7 7 3 4 4 4 7 7 avem:

• platourile 1 1 1 și 4 4 4 ambele având lungimea 3;
• platourile 7 7 (cel care începe în poziția a patra) și 7 7 (cel care începe pe poziţia a zecea), ambele având lungimea 2;
• platoul 3 care are lungimea 1.

În schimb nu avem platoul 7 7 7 7 deoarece cele patru elemente egale cu 7 nu sunt pe poziții consecutive!

Asupra unui șir se poate efectua următoarea operație:

1. se extrage un platou la alegere;
2. se inserează platoul extras la pasul anterior într-o poziție la alegere din șirul rezultat după extragere.

De exemplu, dacă avem următorul șir inițial: 2 2 5 0 5 8 8 8 4 9 9 9 0 0 2 2 8 extragem platoul 2 2 format din elementele aflate în penultima și antepenultima poziție și obținem șirul: 2 2 5 0 5 8 8 8 4 9 9 9 0 0 8

În șirul rezultat inserăm platoul 2 2 (pe care l-am extras la pasul anterior) în poziția a doua și obținem șirul: 2 2 2 2 5 0 5 8 8 8 4 9 9 9 0 0 8.

Cerința

Să se scrie un program care citește un șir de n numere naturale din intervalul [0,10000] și un număr k și determină:

1. lungimea maximă a unui platou care poate să apară în șir în urma efectuării operației de mai sus de maxim k ori;
2. elementul din care este format platoul obținut după cele k operații.

Date de intrare

Programul va citi:

• pe prima linie un număr natural k;
• pe a doua linie un număr natural n;
• pe a treia linie un șir de n numere naturale separate prin câte un spațiu.
• pe a patra linie p, care reprezinta cerința; p poate fi 1 sau 2

Date de ieșire

Programul va afișa lungimea maximă a unui platou care poate să apară în șir în urma efectuării celor două operații de maxim k ori sau elementul din care este format platoul.

Restricții și precizări

• 1 ≤ n ≤ 1000000
• 1 ≤ k 100
• pentru cerința 1 – 50% din punctaj
• pentru cerința 2 – 50% din punctaj
• dacă sunt mai multe platouri de lungime maxima se va afișa cel format din valoarea cea mai mare
• toate testele au soluție

Exemplul 1

Intrare

2
16 
2 2 5 0 5 8 8 8 4 9 9 9 0 8 2 2
1 

Iesire

4

Exemplul 2

Intrare

2
16 
2 2 5 0 5 8 8 8 4 9 9 9 0 8 2 2
2

Iesire

8

Explicație

În urma executării celor două operații pot să apară platouri de lungime maximă 4 în două moduri: 2 2 2 2 respectiv 8 8 8 8.