«Әрбір бастаманың соңы болуы тиіс»
$A = (a_1, a_2, \dots, a_m)$ тізбегі үшін анықтайық:
- ең ұзын қатаң өспелі ішкі тізбектің ұзындығы: $$\text{LIS}(A) = \max\{k \mid \exists 1 \le i_1 < i_2 < \dots < i_k \le m, a_{i_1} < a_{i_2} < \dots < a_{i_k}\}$$
- ең ұзын қатаң кемімелі ішкі тізбектің ұзындығы: $$\text{LDS}(A) = \max\{k \mid \exists 1 \le i_1 < i_2 < \dots < i_k \le m, a_{i_1} > a_{i_2} > \dots > a_{i_k}\}$$
Кез келген $A$ тізбегі үшін $f(A)$ мәнін келесі шарттарды қанағаттандыратын ең үлкен бүтін $k$ саны ретінде анықтайық:
$k$ нақты $x_1, x_2, \dots, x_k$ сандары табылады. Оларды ретімен $A$ тізбегінің соңына қосқаннан кейін, біз жаңа $B = (a_1, a_2, \dots, a_m, x_1, x_2, \dots, x_k)$ тізбегін аламыз және келесі шарттар орындалады:
- $B$ тізбегіндегі барлық элементтер жұп-жұбымен әртүрлі;
- $\text{LIS}(B) = \text{LIS}(A)$;
- $\text{LDS}(B) = \text{LDS}(A)$.
Енді ұзындығы $n$ болатын $P = (P_1, P_2, \dots, P_n)$ алмастыруы берілген. Әрбір $P^{(i)} = (P_1, P_2, \dots, P_i)$ префиксі үшін $f(P^{(i)})$ мәнін есептеп, барлық жауаптарды шығаруыңыз керек.
«Бір күні мен сенің жаныңа ораламын»
Кіріс деректері
Бірінші жолда тесттер санын білдіретін бүтін $T$ ($1 \le T \le 10^5$) саны берілген.
Әрбір тест үшін:
- Бірінші жолда бүтін $n$ ($1 \le n \le 2 \cdot 10^5$) саны берілген;
- Екінші жолда ұзындығы $n$ болатын алмастыруды білдіретін $n$ бүтін $P_1, P_2, \dots, P_n$ ($1 \le P_i \le n$) сандары берілген.
Барлық тесттер бойынша $n$ сандарының қосындысы $2 \cdot 10^5$ мәнінен аспайтынына кепілдік беріледі.
Шығыс деректері
Әрбір тест үшін жауаптарды білдіретін $n$ бүтін саннан тұратын бір жолды шығарыңыз.
Мысалдар
Кіріс 1
5 2 1 2 3 1 3 2 4 3 4 1 2 5 2 5 1 3 4 6 3 6 2 1 4 5
Шығыс 1
0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 2 1 2