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

\begin{document}

\renewcommand{\tl}{$2$ сек.}
\renewcommand{\ml}{$512$ MB}
\problem{Задача С1. ФИНАНСОВ  АНАЛИЗ  НА  АКЦИИ}
\addauthor{Автор: Кинка Кирилова-Лупанова}{2026}{06}{15}
\renewcommand{\header}{
	НАЦИОНАЛЕН ЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА\\
 \vspace{0.1cm}
	\textbf{Пловдив, }\textbf{12 - 14 юни  2026 г.}\\
	\vspace{0.1cm}
	\textbf{Група C, 7 - 8}\textbf{ кла}\textbf{с}
}

\begin{wrapfigure}{r}{0.35\textwidth}
	\begin{adjustbox}{width=0.35\textwidth}
		\includegraphics{stock.jpg}
	\end{adjustbox}
\end{wrapfigure}
На фондовата борса се наблюдава стойността на една акция за всеки от $n$ последователни дни. Стойностите се описват с $a_1,a_2,…,a_n$, където $a_i$ е цената на акцията в $i$-тия ден.

Анализаторите разглеждат последователни времеви интервали с фиксирана дължина $k$, за да оценят стабилността на пазара.  Например: за даден интервал от дни $b_1,b_2,…,b_m$,  разглеждат всички подинтервали с дължина $k$:
$[b_1, \ldots, b_k],\ [b_2, \ldots, b_{k+1}],\ \ldots,\ [b_{m-k+1}, \ldots, b_m]$.

 Напишете програма \texttt{\textbf{stock}}, която отговоря на $q$ заявки от следния вид: за дадени $l$, $r$  и $k$ да се намери сумата от минимумите на всички подинтервали с дължина $k$ в $[a_l, ..., a_r]$.


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

От втория ред на стандартния вход се въвеждат $n$ цели числа  $a_1,a_2,…,a_n$ – стойностите на акцията.

В следващите $q$ реда са дадени заявките. В $i$-тия от тях са дадени три цели числа $l_i, r_i$ и $k_i$ — лявата и дясната граница на интервала и дължината на подинтервала в $i$-тата заявка.


\subsection{Изход}
На стандартния изход програмата трябва да изведе $q$ реда с отговорите на заявките.

В $i$-тия ред изведете едно единствено число — сумата от минимумите на всички подинтервали с дължина $k_i$ в $[a_{l_i}, \dots, a_{r_i}]$.        

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $1 \leq n, q \leq 100\ 000$
	\item $1 \leq  a_i  \leq 10^9$
	\item $1 \leq  l_i  \leq r_i \leq n$
	\item $1 \leq  k_i  \leq r_i-l_i+1$
  \end{itemize}  

     \subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{Допълнителни ограничения} \\
		\hline
		$1$ & $15$ & $  n, q, k_i \leq 500$  \\ 
		\hline
		$2$ & $15$ & $ n \times q \leq 10^8$  \\ 
		\hline
		$3$ & $12$ & $ n, k_i \leq 10^4$   \\ 
		\hline
		$4$ & $13$ & $ a_i \leq 2 $  \\ 
		\hline
			$5$ & $11$ & $ a_i \leq 20 $  \\ 
		\hline
			$6$ & $12$ & $ l_i = 1;  r_i = n $  \\ 
		\hline
			$7$ & $22$ & $ - $  \\ 
		\hline
	\end{tblr}
	
\end{table}
  
  
\subsection{Примери}
\begin{table}[H]
	\begin{tblr}{|l|l|}
		\hline
		\textbf{Вход} & \textbf{Изход}  \\
		\hline
		\texttt{\makecell[lt]{6 3\\
4 6 1 2 5 3\\
2 5 2\\
2 4 1\\
1 6 6
\\ }}
		& 
		\texttt{\makecell[lt]{4\\
		    9\\
		    1\\
		}}
		
		 
\\
		\hline 
	\end{tblr}
\end{table}
\FloatBarrier
	
\end{document}
