Kaydırmalı Sıralama

Giriş

Her testin ilk satırı tek bir tam sayı $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) — test durumlarının sayısını içerir.

Her test durumunun ilk satırı tek bir tam sayı $n$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \le n \le 2 \cdot 10^5) — $a$ dizisinin uzunluğunu içerir.

Her test durumunun ikinci satırı $n$ tam sayı $a_{1}, a_{2}, ..., a_{n}$ a_1 , a_2 , ... , a_n ( $1 \leq a_{i} \leq 2 \cdot 1 0^{5}$ 1 \le a_i \le 2\cdot 10 ^ 5) — $a$ dizisini içerir.

Tüm test durumları üzerinden $n$ toplamının $2 \cdot 1 0^{5}$ 2 \cdot 10^5 değerini aşmadığı garanti edilir.

Çıktı

Her test durumu için tek bir tam sayı, $a$ dizisini sıralamak için gereken en az işlem sayısını yazdırın.

Örnekler

Örnek 1

Loading

Not

İlk test durumunda $i = 2$ i = 2 seçip bir işlem uygulayarak $[1, 1, 3]$ [1 , 1 , 3] dizisini elde edebilirsiniz.

Puanlama

Alt görev $1$ ( $10$ puan): $\sum n \leq 5$ \sum n \le 5
Alt görev $2$ ( $20$ puan): tüm $i$ için $a_{i} = 2^{x} - 1$ a_i = 2^x - 1 ( $1 \leq i \leq n$ 1 \le i \le n).
Alt görev $3$ ( $20$ puan): tüm $i$ için $a_{i} \leq 3$ a_i \le 3 ( $1 \leq i \leq n$ 1 \le i \le n).
Alt görev $4$ ( $150$ puan): Ek kısıt yoktur.