Адина «Нарутоны» \(1\)-сериядан \(m\)-серияға дейін қайта қарауды шешті.

Бір кинотеатрда күн сайын «Нарутоның» сериялары бірдей ерекше ретпен көрсетіледі. Күн сайын қатарынан дәл \(n\) көрсетілім өтеді. \(i\)-көрсетілімде нөмірі \(a_i\) болатын серия көрсетіледі, мұнда \(1 \le a_i \le m\). Бұл тәртіп күн сайын өзгермейді.

Адина билеттер сатып ала алады. Бір билет былай жұмыс істейді: ол \(l\) индексін таңдайды (\(1 \le l \le n-k+1\)), және билет осы күнгі қатарынан \(k\) көрсетілімнен тұратын блокқа \(l, l+1, \dots, l+k-1\) жарамды болады. Осы билетпен Адина таңдалған блоктың ішіндегі кез келген көрсетілімдер жиынын көре алады (кез келген көрсетілімді өткізіп жіберуге болады). Егер ол бірнеше көрсетілімді көрсе, оларды уақыт бойынша табиғи тәртіпте (индекстердің өсуі бойынша) көреді.

Адина серияларды \(1,2,\dots,m\) дәл осы тәртіппен көргісі келеді: алдымен ол \(1\)-серияны көруі керек, содан кейін (уақыт бойынша кейін, мүмкін басқа күні) \(2\)-серияны, кейін \(3\)-серияны және т.с.с. \(m\)-серияға дейін.

Осыны орындау үшін сатып алынуы тиіс билеттердің ең аз санын табыңыз. Егер бұл мүмкін болмаса, \(-1\) шығарыңыз.

Енгізу

Бірінші жолда бүтін сан \(t\) \((1 \le t \le 10^4)\) — тесстер саны берілген.

Келесі \(t\) тесттер кіріс деректерімен жалғасады.

Әр набордың бірінші жолында үш бүтін сан \(n\), \(m\), \(k\) \((1 \le n,m,k \le 3\cdot 10^5,\ k \le n)\) берілген.

Әр набордың екінші жолында \(n\) бүтін сан \(a_1,a_2,\dots,a_n\) \((1 \le a_i \le m)\) берілген.

Барлық наборлар бойынша \(n\) санының қосындысы \(3\cdot 10^5\)-тен аспайтынына кепілдік беріледі.

Шығару

Әр тест үшін бір бүтін сан шығарыңыз — билеттердің минималды саны, немесе \(-1\), егер бұл мүмкін болмаса

Бағалау жүйесі

Мәселе \(6\) кіші мәселеден тұрады.

Мысалдар

Енгізу 1

3
7 5 4
2 1 3 4 2 5 3
5 4 3
1 2 3 1 2
4 4 4
4 3 2 1

Жауап 1

2
-1
4

Ескертпелер

Бірінші мысалда, оңтайлы түрде:

• 1-күн: \(l=2\) сегментіне билет сатып алу (көрсетілімдер \(2..5\): \([1,3,4,2]\)), \(1\) және \(2\) серияларын көру (басқаларын өткізіп жіберу).

• 2-күн: \(l=3\) сегментіне билет сатып алу (көрсетілімдер \(3..6\): \([3,4,2,5]\)), \(3,4,5\) серияларын көру (серия \(2\) өткізіп жіберу).

Нәтижесінде \(2\) билет қажет