\documentclass[12pt]{article}
\input{structure.tex}
\renewcommand{\bottomtitlespace}{3cm}
\usepackage{graphicx}
\newcommand{\header}{
	НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА\\
	Общински кръг, 20 декември 2025 г.\\
	Група B, 9 – 10 клас\\
}

\begin{document}

\newcommand{\tl}{$0.75$ сек.}
\newcommand{\ml}{$256$ MB}
\problem{Задача B1. Въже}

Дамян обича адреналина. Днес той си е наумил, че иска да се катери по блоковете в определен жилищен квартал. Пред него се намират $N$ на брой сгради, всяка от които може да бъде представена като правоъгълник с ширина $1$ метър и височина $h_i$ метра. Долният ляв ъгъл на всеки правоъгълник лежи на абсцисата и съвпада с долния десен ъгъл на предходния правоъгълник (долният ляв ъгъл на първата сграда е точката с координати $(0,0)$). 

Дамян в момента се намира в точката $(0,0)$ и иска да се придвижи до точката $(N,0)$ (долният десен ъгъл на последната сграда). Той може да направи това, като се движи по контура на фигурата, описана от сградите (тоест се движи по стените и покривите на блоковете). При катеренето нагоре и спускането надолу Дамян изминава $|h_{i+1}-h_i|$ метра (където въвеждаме фиктивните $h_0=h_{N+1}=0$), а при преминаването от ляв до десен край на покрив на сграда -- по $1$ метър.

За да улесни малко работата си, той е помолил Александър да спусне въже между някои две от сградите. Въжето се връзва от левия край на покрива на някоя сграда $i$ до левия край на покрива на друга \textbf{по-дясна} и \textbf{не по-ниска} сграда $j$ ($1 \leq i < j \leq N$ и $h_i \leq h_j$). За да премине по въжето, Дамян трябва да измине $\sqrt{(j-i)^2 + (h_j-h_i)^2}$ метра. Важно е да се отбележи, че въжето може видимо да пресича други сгради. Александър може да спусне \textbf{най-много едно въже}. Неговата цел е да минимизира пътят на Дамян от началната до крайната точка.

Вашата задача е да напишете програма \textbf{rope}, която да изчислява минималния път, който Дамян трябва да измине, за да се предвижи от $(0,0)$ до $(N,0)$ при оптимално поставяне на въжето от страна на Александър. Също така, програмата Ви ще трябва да решава задачата за $T$ на брой под-теста.

\subsection{Вход}
От първия ред на стандартния вход се въвежда едно естествено число $T$ -- броят на под-тестовете.
След това се въвежда информацията за всеки от тези $T$ на брой под-теста: на нов ред се въвежда числото $N$ (броят на сградите), следван от нов ред с $N$ на брой числа $h_i$, всяко от които означава височината на $i$-тата сграда.

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

Отговорът Ви за даден под-тест се счита за верен, ако абсолютната или релативната грешка не надхвърля $10^{-6}$. Именно, ако отговорът Ви е \textit{A}, а истинският отговор е \textit{B}, то отговорът Ви се приема като коректен, ако $\frac{|A - B|}{max(1,|B|)} \leq 10^{-6}$.

\textit{Забележка: За да изведете дробно число с определен брой цифри (например 6) след десетичната точка може да използвате следния код:}

\begin{verbatim}
#include <iomanip>
std::cout << std::setprecision(6) << fixed << x;
\end{verbatim}

\subsection{Ограничения}
\vspace{0.5em}
\begin{itemize}
	\item $1 \leq N \leq 10^6$
	\item $1 \leq h_i \leq 10^6$
	\item $1 \leq T \leq 7$
\end{itemize}

\subsection{Тестове}
\vspace{0.5em}
\begin{itemize}
	\item В $10\%$ от тестове $N: \leq 200$
	\item В други $15\%$ от тестове: $N \leq 5000$
	\item В други $15\%$ от тестове: $N \leq 2 \times 10^5$ и $h_i \leq 3$
	\item В други $35\%$ от тестове: $N \leq 2 \times 10^5$
	\item В останалите $25\%$ от тестове няма допълнителни ограничения.
\end{itemize}

\subsection{Примери}
\begin{table}[H]
	\begin{tblr}{|l|l|X[j]|}
		\hline
		\textbf{Вход} & \textbf{Изход} & \textbf{Допълнително обяснение}\\
		\hline
		\texttt{\makecell[lt]{1\\5\\5 2 1 6 3}} & \texttt{16.162278} & \begin{adjustbox}{width=0.35\textwidth, valign=t, center, margin=0cm 0.1cm 0cm 0.1cm}
				\includesvg[inkscapelatex=false]{example1}
		\end{adjustbox} Червената линия показва оптималното придвижване. Забележете, че не може да се спусне въже между сгради 1 и 5, тъй като сграда 1 е по-висока.\\
		\hline
            \texttt{\makecell[lt]{1\\4\\4 2 3 3}} & \texttt{13.236068} & \begin{adjustbox}{width=0.35\textwidth, valign=t, center, margin=0cm 0.1cm 0cm 0.1cm}
            		\includesvg[inkscapelatex=false]{example2}
            \end{adjustbox} Обърнете внимание на въжето между сгради 2 и 4 - позволено е въжетата да пресичат сгради, затова няма проблем, че преминваа през сграда номер 3.\\
		\hline
	\end{tblr}
\end{table}

\end{document}
