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

\renewcommand{\header}{
	ЗИМНИ СЪСТЕЗАНИЯ ПО ИНФОРМАТИКА\\
	``Д-р Младен Манев"\\
	Габрово, 31 януари 2026 г.\\
	Група T (отборен формат)
}

\begin{document}

\renewcommand{\tl}{$1$ сек}
\renewcommand{\ml}{$256$ MB}
\problem{Задача T6. БУТИЛКИ}

В завода за бутилки пристигнала заявка за производството на $n$ бутилки от закалено стъкло. Бутилките, които трябва да се произведат не са еднакви. При закаляването си, бутилка с номер $i$ трябва да стои за точно $t_i$ секунди в пещта за закаляване.

Заводът разполага с еднакви пещи за закаляване, които имат със следните характеристики:
\begin{itemize}
	\item имат неограничен капацитет от бутилки;
	\item поради наличността на само един отвор, през който влизат и излизат бутилки, принципът, на който работят, е LIFO -- последната влязла бутилка в пещта е първата, която ще излезе;
	\item пъхането на една бутилка отнема 1 секунда и бутилката е започнала процеса си на закаляване \textbf{след} като е изтекла тази секунда;
	\item изваждането на една бутилка отнема 1 секунда и за бутилката е приключила си процеса на закаляване точно \textbf{след} като е изтекла тази секунда;
	\item след като е извадена бутилка от пещта, \textbf{не може} друга бутилка да бъде пъхната за закаляване в същата пещ;
	\item след като е използвана една пещ, тя не е годна за повторна употреба, защото трябва бъде почистена и заредена повторно с гориво.
\end{itemize}
Заводът също има право да закалява бутилките в произволен ред.

Нека имаме една пещ и $n=2$ бутилки с времена на закаляване $t_0=2$ и $t_1=1$. Ако сложим бутилка $0$ и след това бутилка $1$, то ще трябва да извадим бутилка $1$, защото тя ще е престояла точно 1 сек. в момента на изваждането си, но ако след това е опитаме да извадим бутилка $0$, то тя ще е престояла 3 сек., което е повече от желаното. Ако пък сложим първо бутилка номер $1$, то тогава ще трябва веднага след това да я извадим, което няма да ни позволи да поставим бутилка 0 след това, заради особеностите на пещите. Изводът е, че за дадения пример, ще ни трябват най-малко две пещи, за да изпълним заявката.

От ръководството на завода си задават въпроса: „колко най-малко пещи ще им са нужни, за да изпълнят поръчката, без да се налага да почистват пещи по време на изпълнението на поръчката?“ Напишете програма, която отговаря на техният въпрос.

\subsection{Вход}
На първия ред от стандартния вход ще ви е подадено едно цяло число $n$ -- броят на бутилките в заявката. На втория ред ще получите $n$ на брой естествени числа -- времената $t_i$.

\subsection{Изход}
На първия и единствен ред от стандартния изход, изведете едно цяло число число, равно на търсения минимален брой нужни пещи.

\subsection{Ограничения}
\begin{itemize}
\item $1 \le n \le 200~000$
\item $1 \le t_i \le 10^9$
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{Необходими подзадачи} & \textbf{Допълнителни ограничения} \\
        \hline
        $0$ & $0$ & -- & Примерните тестове \\ 
		\hline
		$1$ & $12$ & -- & $n \le 3$ \\ 
		\hline
		$2$ & $15$ & $1$ & $n \le 7$ \\ 
		\hline
		$3$ & $15$ & -- & $t_i < t_{i+1}$ за всяко $i < n$ \\
		\hline
		$4$ & $18$ & -- & $t_i$ е четно за всяко $i < n$ \\
		\hline
		$5$ & $20$ & $2$ & $n \le 1000$ \\
		\hline
        $6$ & $20$ & $1-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\\
        1 2
		}
		}
		& 
		\texttt{\makecell[lt]{2}
		}
		& 
             {Примерът от условието.}
            \\
		\hline
        \texttt{\makecell[lt]
		{3\\
        3 6 1
		}
		}
		& 
		\texttt{\makecell[lt]{1}
		}
		& 
             {Достатъчно е да използваме една пещ, като реда на пъхането на бутилките в пеща е $1$, $0$, $2$.}
            \\
		\hline
		\texttt{\makecell[lt]
		{5\\
        1 2 4 3 2
		}
		}
		& 
		\texttt{\makecell[lt]{3}
		}
		& 
             {Достатъчно ни е да използваме 3 пещи. В първата влизат бутилки $3$ и $0$, във втората - $2$ и $1$, а в третата - $4$.}
            \\
		\hline
	\end{tblr}
\end{table}
\FloatBarrier
	
\end{document}
