% !TeX program=lualatex

\documentclass[12pt]{article}
\input{structure.tex}
\renewcommand{\bottomtitlespace}{0cm}

\begin{document}
	
\renewcommand{\tl}{$0.3$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача GT11. ОБУВКИ}
\renewcommand{\header}{
	ТРЕНИРОВЪЧНО СЪСТЕЗАНИЕ\\
	НА РАЗШИРЕНИЯ НАЦИОНАЛЕН ОТБОР\\
	София, 24 юни 2026 г.\\
	Група G
}

Момо бил човек, който харесвал винаги да му е подредено. Той притежавал $N$ чифта обувки, като всеки един чифт се състои от 2 обувки от един и същи размер -- една лява и една дясна.
Когато той се прибрал забелязал, че някой се е пошегувал с него и му е разбъркал обувките. Сега те са наредени в редица от $2N$ елемента, номерирани от $0$ до $2N - 1$ от ляво надясно.

Сега Момо иска да си нареди обувките като за него редицата от обувки е подредена, ако са изпълнени следните условия за всяко $i \ (0 \leq i \leq N - 1)$: 
\begin{itemize}
	\item Обувките на позиции $2i$ и $2i + 1$ са от един и същи размер.
	\item Обувката на позиция $2i$ е лява, а обувката на позиция $2i + 1$ е дясна.
\end{itemize}

За да постигне целта си, Момо може да разменя обувки, които са на съседни позиции. Вашата задача е да напишете програма, която намира минималния брой размени, чрез които е възможно Момо да подреди обувките си. Това винаги е възможно.

\subsection{Вход}

От първия ред на стандартния вход се въвежда числото $N$ - броя на чифтовете.
На втория ред следват $2N$ числа, това е масив $A$, който описва редицата от обувки.
За $i \ (0 \leq i \leq 2N - 1)$ $A_i$ е ненулево число, което описва обувката на позиция $i$.
Размерът на обувката е $|A_i|$, а знакът на числото показва дали обувката е лява или дясна. Ако $A_i$ е отрицателно число, то обувката на позиция $i$ е лява, а ако е положително число, то обувката на позиция $i$ е дясна.

\subsection{Изход}

На един ред на стандартния изход изведете едно число - минималния брой размени, чрез които е възможно Момо да подреди обувките си.

\subsection{Ограничения}
\begin{itemize}
	\item $1 \leq N \leq 10^{5}$, за всяко $i \ (0 \leq i \leq 2N - 1)$, $1 \leq |A_i| \leq N$.
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|X[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{\makecell{Необходими\\подзадачи}} & $N$ & \textbf{Други ограничения} \\
        \hline
        	$0$ & $0$ & $-$ & $-$ & Примерните тестове. \\ 
        \hline
			$1$ & $10$ & $-$ & $= 1$ & -- \\
		\hline
			$2$ & $20$ & $0-1$ & $\leq 8$ & -- \\
		\hline
			$3$ & $20$ & $-$ & $\le 10^5$ & Всички обувки са с еднакъв размер.\\
		\hline
			$4$ & $15$ & $-$ & $\le 10^5$ & Всички обувки на позиции $0,..,N-1$ са леви, а всички обувки на позиции $N,..,2N-1$ са дeсни.  Също така, за всяко $i \ (0 \leq i \leq N - 1)$ , обувките на позиции $i$ и $i + N$ са с еднакъв размер \\
		\hline
			$5$ & $20$ & $0-2$ & $\le 10^3$ & -- \\
		\hline
			$6$ & $15$ & $0-5$ & $\le 10^5$ & -- \\
		\hline
		\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички нейни тестове, както и тестовете на необходимите ѝ подзадачи.}
\end{table}


\subsection{Пример}
\begin{table}[H]
	\begin{tblr}{|l|l|X[j]|}
		\hline
		\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение на примера} \\
		\hline
		\texttt{\makecell[lt]{
		    2\\
		    2 1 -1 -2
		}} & 
		\texttt{4} & 
		{Момо може да постигне валидна подредба с $4$ размени.
		Например, той може първо да размени обувки $1$ и $-1$, след това $1$ и $-2$,
		после $-1$ и $-2$ и накрая $2$ и $-2$. Той ще достигне до валидна подредба:
		$[−2,2, −1,1]$. Не е възможно да се достигне до валидна подредба с по-малко от $4$ размени, поради което процедурата трябва да върне стойност
		$4$.}\\
		\hline
		\texttt{\makecell[lt]{
		    3\\
		    -2 2 2 -2 -2 2
		}} & 
		\texttt{1} & 
		{Момо може да размени обувките на позиции $2$ и $3$ и да постигне
		валидната подредба $[−2,2, −2,2, −2,2]$ , следователно процедурата трябва
		да върне стойност $1$.}\\
		\hline
	\end{tblr}
\end{table}

\end{document}
