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

\renewcommand{\header}{
	ЗИМНИ ОНЛАЙН СЪСТЕЗАНИЯ ПО ИНФОРМАТИКА\\ ``Д-р Младен Манев''\\
	31 януари 2026 г.\\
	Група B -- 9, 10 клас
}

\begin{document}

\renewcommand{\tl}{$1$ сек}
\renewcommand{\ml}{$256$ MB}
\problem{Задача B3. ЗАСТРОЯВАНЕ}

И ето че най-вече дошъл реда на новата улица „Шепот на щурци“ в квартал Старост 17 във въображаемия град Горна Мъгла да бъде застроен. Само едната страна на улицата може да бъде застроена, поради факта, че от другата ѝ страна има езеро. Номерата на имотите, от страната която може да бъде застроена са номерирани с числа в интервала [$0$, $\inf$).

Поради високото търсене на имоти, всички строителни фирми се канят да строят блокове, като заявленията за строеж изглеждат по следния начин: две числа $a_i$ и  $b_i$, които показват че фирмата подала заявката се ще построи по един етаж на всички блокове, които имат номера на улицата в интервала [$a_i$, $b_i$]. Съответно, ако на даден номер не е имало блок, то строителят ще построи едноетажен блок.

Също заради особеността на тази улица, градското планиране са длъжни да изпълнят няколко изисквания:
\begin{itemize}
	\item трябва да издадат разрешение за строеж само на последователно подадени заявления;
	\item нека броят на получените разрешения за строеж е равен на $p$. След като всички блокове бъдат завършени, последователният интервал от блокове с височина $p$ трябва да има дължина в интервала [$d_1$, $d_2$].
\end{itemize}

От градското планиране си задали въпроса: „колко различни последователни заявки могат да одобрят, така че изискванията да бъдат изпълнени?“ Напишете програма, която отговаря на техният въпрос.

\subsection{Вход}
На първия ред от стандартния вход ще Ви се подадат две цели числа: $d_1$ и $d_2$. На втория ред ще Ви е подадено $n$ - броят на получените заявки за строеж. На следващите $n$ реда ще се подадат по две цели числа $a_i$ и $b_i$ - интервалът на заявката за строеж.

\subsection{Изход}
На първия и единствен ред от стандартния изход, изведете едно цяло число число, равно на търсеният брой на различните последователности от заявки, които могат да бъдат одобрени.

\subsection{Ограничения}
\begin{itemize}
\item $1 \le n \le 200~000$
\item $0 \le d_1 \le d_2 \le 10^9$
\item $0 \le a_i \le b_i \le 10^9$
\end{itemize}

\newpage

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{Необходими подзадачи} & \textbf{Допълнителни ограничения} \\
        \hline
        $0$ & $0$ & -- & Примерните тестове \\ 
		\hline
		$1$ & $12$ & -- & $n \le 100$ \\
		\hline
		$2$ & $18$ & -- & $a_i \le a_{i+1}$ за всяко $i$ \\
		\hline
		$3$ & $18$ & $1$ & $n \le 1000$ \\
		\hline
		$4$ & $20$ & -- & $b_i - a_i < 30$ за всяко $i$ \\
		\hline
        $5$ & $32$ & $1-5$ & -- \\
		\hline
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и за необходимите подзадачи.}
\end{table}

\subsection{Примери}
\begin{table}[H]
	\begin{tblr}{|l|l|X[j]|}
		\hline
		\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение} \\
		\hline
		\texttt{\makecell[lt]
		{1 2\\
		 4\\
		 2 5\\
		 3 6\\
		 4 7\\
		 5 5
		}
		}
		& 
		\texttt{\makecell[lt]{5}
		}
		& 
             {Всяка последователност, която съдържа последната последната заявка, би имала един блок с височина p, който ще се намира на номер 5. От тук има четири възможни последователности. Последната пета е ако се разрешат първите три заявки за строеж.}
            \\
		\hline
        \texttt{\makecell[lt]
		{0 1\\
		 6\\
		 2 5\\
		 2 3\\
		 2 2\\
		 5 5\\
		 4 5\\
		 2 5
		}
		}
		& 
		\texttt{\makecell[lt]{15}
		}
		& 
             {Всички възможни последователности, които включват заявките 3 или 4 или и двете биха отговаряли на изискванията.}
            \\
		\hline
	\end{tblr}
\end{table}
\FloatBarrier
	
\end{document}
