\documentclass[12pt]{article}
\input{structure.tex}
\fancyhead[R]{
	\begin{minipage}{\textwidth}
		\raggedleft
		\includegraphics[width=2cm]{./logo2.png}
	\end{minipage}
}
\renewcommand{\bottomtitlespace}{3cm}

\begin{document}

\renewcommand{\tl}{$0.8$ сек.}
\renewcommand{\ml}{$256$ MB}
\problem{Задача OS13. ПОДОБРЕНИЯ}
\addauthor{Автор: Пано Панов}{2026}{08}{29}
\renewcommand{\header}{
	НАЦИОНАЛНА ШКОЛА ПО ИНФОРМАТИКА\\
	ОТБОРНО СЪСТЕЗАНИЕ\\
	Габрово, 29 август 2026 г.\\
	8 – 10 клас
}

\begin{wrapfigure}{r}{0.25\textwidth}
	\begin{adjustbox}{width=0.25\textwidth}
		\includegraphics{image}
	\end{adjustbox}
\end{wrapfigure}
Зоя -- малката сестра на Петър преглежда редовно неговите тетрадки по математика и дори променя някои числа в тях. Един ден Зоя открива поредица от нули и решава да я ``подобри''. Петър открива намесата на Зоя и се опитва да разбере колко пъти Зоя е правила подобрения в редицата. След кратко разпитване Зоя обяснява, че при всяко подобрение е избирала непрекъснат сегмент от редицата и е увеличавала стойностите на всички елементи от сегмента с някакво цяло положително число. Освен това, избрания сегмент не се пресичал частично с никой друг, но може да се припокрива или изцяло да се съдържа в друг. 

Помогнете на Петър, като напишете програма \textbf{\texttt{upgrade}}, която намира минималния възможен брой ``подобрения'', които е извършила Зоя. 

\subsection{Вход}
От първия ред на стандартния вход се въвежда цялото число $n$ -- дължината на редицата. 
От втория ред се въвеждат $n$ неотрицателни цели числа $a_i$, разделени с по един интервал --  стойностите на елементите на редицата след подобренията на Зоя.

\subsection{Изход}
На единствения ред се извежда $m$ -- минималният възможен брой подобрения.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $1 \leq n \leq 10^7$
	\item $0 \leq a_i \leq 3.10^9$
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{Необходими подзадачи} & $n$ \\
		\hline
		$1$ & $30$ & $-$ & $\le 10^3$ \\ 
		\hline
		$2$ & $30$ & $1$ & $\le 10^5$ \\ 
		\hline
		$3$ & $40$ & $1-2$ & $\le 10^7$ \\ 
		\hline
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
\end{table}
\FloatBarrier

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

\subsection{Обяснение}
За първо подобрение Ева избира сегмент $[a_1, a_5]$ и увеличава всички елементи на сегмента с $2$. Второто подобрение, което Ева избира, е сегмент $[a_2, a_4]$ и увеличава всички елементи на сегмента с $1$.
		
\end{document}