% !TeX program=lualatex

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

\begin{document}
	
	\renewcommand{\tl}{$0.1$ сек.}
	\renewcommand{\ml}{$256$ MB}
	\problem{Задача CT3. СКЛАД}
	\addauthor{Автор: Петър Петров}{2030}{12}{20}
	\renewcommand{\header}{
		ТРЕНИРОВЪЧНО СЪСТЕЗАНИЕ\\
		НА РАЗШИРЕНИЯ НАЦИОНАЛЕН ОТБОР\\
		София, 2 май 2026 г.\\
		Група C, 7 -- 8 клас
	}
	
	В голям склад има $n$ кашона, подредени в редица и номерирани от $1$ до $n$.  
	Всеки кашон има етикет -- цяло число $a_i$, което обозначава вида на съдържанието му.
	
	Инспекторът на склада извършва проверки. При всяка проверка той избира интервал от кашони $[l, r]$.
	
	Един вид кашони с етикет $x$ се нарича \textit{правилно подреден} в интервала, ако:
	
	\[
	\text{в интервала има точно } x \text{ кашона с етикет } x.
	\]
	
	Например, ако $x = 3$, то в разглеждания интервал трябва да има точно $3$ кашона с етикет $3$.
	
	\textbf{Забележка:} броим различните стойности $x$, които удовлетворяват условието.
	
	Напишете програма \texttt{\textbf{warehouse.cpp}}, която за всяка проверка намира броя на правилно подредените видове кашони.
	
	\subsection{Вход}
	От първия ред на стандартния вход се въвеждат две цели числа $n$ и $q$ -- съответно броят на кашоните и броят на проверките.
	
	От втория ред се въвеждат $n$ цели числа $a_1, a_2, \dots, a_n$ -- етикетите на кашоните.
	
	Всеки от следващите $q$ реда съдържа по две цели числа $l$ и $r$ -- границите на проверката.
	
	\subsection{Изход}
	За всяка заявка изведете на отделен ред едно цяло число -- броя на различните етикети $x$, за които има точно $x$ кашона с етикет $x$ в интервала $[l, r]$.
	
	\subsection{Ограничения}
	\begin{itemize}
		\item $1 \leq n, q \leq 100~000$
		\item $1 \leq a_i \leq 10^6$
		\item $1 \leq l \leq r \leq n$
	\end{itemize}
	\FloatBarrier
	
	\subsection{Подзадачи}
	\begin{table}[H]
		\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|X[c,m]|}
			\hline
			\textbf{Подзадача} & \textbf{Точки} & \textbf{\makecell{Необходими\\подзадачи}} & $n, q$ & \textbf{Други ограничения}\\
			\hline
			$1$ & $10$ & $-$ & $\le 1000$ & \SetCell[r=2]{}{--} \\
			\hline
			$2$ & $20$ & $1$ & $\le 20~000$ & \\
			\hline
			$3$ & $20$ & $-$ & $\le 100~000$ & Всички заявки са с $l = 1$. \\
			\hline
			$4$ & $25$ & $-$ & $\le 100~000$ & Всички $a_i \le 100$. \\
			\hline
			$5$ & $25$ & $1-4$ & $\le 100~000$ & Няма допълнителни ограничения. \\
			\hline
		\end{tblr}
		\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
	\end{table}
	\FloatBarrier
	
	\pagebreak
	\subsection{Примери}
	\begin{table}[H]
		\begin{tblr}{width={\linewidth},colspec={|X[l]|X[l]||X[l]|X[l]|}}
			\hline
			\textbf{Вход 1} & \textbf{Изход 1} & \textbf{Вход 2} & \textbf{Изход 2} \\
			\hline
\texttt{\makecell[lt]{7 3\\1 2 2 3 3 3 2\\1 7\\1 3\\4 6}} & \texttt{\makecell[lt]{2\\2\\1}} &
\texttt{\makecell[lt]{5 2\\1 1 1 1 1\\1 5\\2 4}} & \texttt{\makecell[lt]{0\\0}}\\
			\hline
		\end{tblr}
	\end{table}
	
	\subsection{Обяснение на пример 1}
	За заявката $[1,7]$:
	\begin{itemize}
		\item етикет $1$ се среща $1$ път $\Rightarrow$ валиден
		\item етикет $2$ се среща $3$ пъти $\Rightarrow$ не е валиден
		\item етикет $3$ се среща $3$ пъти $\Rightarrow$ валиден
	\end{itemize}
	Следователно отговорът е $2$.
	
\end{document}