% !TeX program=lualatex

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

\begin{document}
	
\renewcommand{\tl}{$0.35$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача TS3. ТРОЙКА}
\addauthor{Автор: Иван Лупов (заета)}{2026}{08}{28}
\renewcommand{\header}{
	НАЦИОНАЛНА ШКОЛА ПО ИНФОРМАТИКА\\
	КОНТРОЛНО СЪСТЕЗАНИЕ\\
	Габрово, 28 август 2026 г.\\
	9 – 10 клас
}

Известната задача \texttt{3SUM} е следната: за дадена редица $b_1, b_2, \dots, b_m$ трябва да се изичисли броя тройки $1 \le i < j < k \le m$, такива че $b_i + b_j + b_k = 0$. Понастоящем не е известно решение за тази задача със сложност по-добра от $O(m^2)$.

Тук обаче се намесвате Вие! След неуморни дни работа Вие разработвате линеен алгоритъм за проблема, но за да убедите скептичното жури на НШИ $2026$ ще трябва повече от да решите задачата веднъж. Журито ще Ви даде редица $a_1, a_2, \dots, a_N$ и ще Ви зададе $Q$ въпроса от следния вид ``Решете задачата \texttt{3SUM} за редицата $a_l, a_{l + 1}, \dots, a_r$''.

Напишете програма \texttt{\textbf{3sum}}, която да отговори на тези заявки и да запише името Ви в бъдещите учебници по дизайн и анализ на алгоритми.

\subsection{Вход}

От първия ред на стандартния вход се въвеждат $N$ и $Q$ -- броят елементи в редицата и броят заявки, които журито ще Ви зададе. От втория ред се въвеждат $N$ числа $a_1, a_2, \dots, a_N$. От всеки от следващите $Q$ реда се въвежда по една двойка числа $l_i, r_i$, описваща заявка, на която трябва да отговорите.

\subsection{Изход}

На стандартния изход изведете $Q$ реда, като $i$-тия от тях да съдържа единствено число -- отговорът на съответната заявка.

\subsection{Ограничения}
\begin{itemize}
	\item $1 \le N \le 5~000$
	\item $1 \le Q \le 10^5$
	\item $-10^6 \le a_i \le 10^6$ за $i = 1, 2, \dots, N$
	\item В тестове за около $21$ точки: $N \le 500$.
	\item В тестове за около $50$ точки: $N \le 2~000$.
\end{itemize}

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

\end{document}
