% !TeX program=lualatex

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

\begin{document}

\renewcommand{\tl}{$1$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача GT12. ДОЛЕПЯНЕ}
\addauthor{Автор: Иван Лупов (заета)}{2030}{12}{20}
\renewcommand{\header}{
	ТРЕНИРОВЪЧНО СЪСТЕЗАНИЕ\\
	НА РАЗШИРЕНИЯ НАЦИОНАЛЕН ОТБОР\\
	София, 2 май 2026 г.\\
	Група G
}

Дадена е редица $a$ от $n$ елемента. Позволени са следните два типа модификации:
\begin{itemize}
	\item Ротация: последният елемент от редицата става първи, а всички останали се отдръпват надясно;
	\item Долепяне: долепя се ново число с произволна стойност накрая на редицата.
\end{itemize}

Целта е началната редица да бъде трансформирана чрез поредица от ротации и долепяния до състояние, в което съществува подредица $[l, r]$ от последователни числа, за която е вярно, че:
\begin{itemize}
	\item $r - l + 1 = k$;
	\item за всяко $l \le p \le r$ съществува позиция $l \le q \le r$, такава че $a_q = p$.
\end{itemize}

Напишете програма \textbf{\texttt{extend.cpp}}, която открива \textit{минималния} брой долепяния, които е нужно да се изпълнят, за да е изпълнена целта. Забележете, че броят на изпълнените ротации е без значение.

\subsection{Вход}
От първия ред на стандартния вход се въвежда $n$ -- дължината на редицата. От втория ред на стандартния вход се въвежда $a_1, a_2, \dots a_n$ -- стойностите в редицата.

\subsection{Изход}
На стандартния изход се извежда минималният брой долепяния, които трябва да бъдат изпълнени, за да съществува подредица с описаните свойства.
 
\subsection{Ограничения}
\begin{itemize}
	\item $1 \le k \le n \leq 300~000$;
	\item $1 \le a_i \le n$
\end{itemize}
\FloatBarrier

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|X[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{\makecell{Необходими\\подзадачи}} & $k$ & $n$ & \textbf{Други ограничения}\\
		\hline
		$0$ & $0$ & $-$ & $\le n$ & \SetCell[r=2]{}{$\le 300~000$} & Примерните тестове. \\
		\hline
		$1$ & $14$ & $-$ & $\le 3$ &  & $-$ \\ 
		\hline
		$2$ & $21$ & $0$ & \SetCell[r=4]{}{$\le n$} & $\le 50$ & \SetCell[r=4]{}{--} \\
		\hline
		$3$ & $22$ & $0,2$ & & $\le 3~000$ & \\
		\hline
		$4$ & $21$ & $0,2,3$ & & $\le 80~000$ & \\
		\hline
		$5$ & $22$ & $0-4$ & & $\le 300~000$ & \\
		\hline
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
\end{table}
\FloatBarrier

\newpage
\subsection{Примери}
\begin{table}[H]
	\begin{tblr}{|l|l|}
		\hline
		\textbf{Вход} & \textbf{Изход} \\
		\hline
		\texttt{\makecell[lt]{4 3\\1 4 4 1}} & \texttt{2}\\
		\hline
	\end{tblr}
\end{table}

Могат да се изпълнят следните операции:
\begin{table}[H]
	\begin{tblr}{|l|l|l|}
		\hline
		\textbf{Тип операция} & \textbf{Редица преди} & \textbf{Редица след} \\
		\hline
		Ротация & $[1, 4, 4, 1]$ & $[1, 1, 4, 4]$\\
		\hline
		Долепяне & $[1, 1, 4, 4]$ & $[1, 1, 4, 4, 3]$\\
		\hline
		Ротация & $[1, 1, 4, 4, 3]$ & $[3, 1, 1, 4, 4]$\\
		\hline
		Ротация & $[3, 1, 1, 4, 4]$ & $[4, 3, 1, 1, 4]$\\
		\hline
		Долепяне & $[4, 3, 1, 1, 4]$ & $[4, 3, 1, 1, 4, 5]$\\
		\hline
		Ротация & $[4, 3, 1, 1, 4, 5]$ & $[5, 4, 3, 1, 1, 4]$\\
		\hline
		Ротация & $[5, 4, 3, 1, 1, 4]$ & $[4, 5, 4, 3, 1, 1]$\\
		\hline
		Ротация & $[4, 5, 4, 3, 1, 1]$ & $[1, 4, 5, 4, 3, 1]$\\
		\hline
	\end{tblr}
\end{table}
След изпълнението на операциите съществува поредица от $3$ последователни елемента от трети до пети елемент, в която присъстват $3, 4, 5$, както е нужно, за да е изпълнено условието на задачата.

\end{document}
