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

\begin{document}

\renewcommand{\tl}{$1$ сек.}
\renewcommand{\ml}{$3$ MB}
\problem{Задача E22. НАЙ-ГОЛЯМ ОБЩ ДЕЛИТЕЛ}
\addauthor{Автор: Димитър Добрев}{2026}{03}{16}
\renewcommand{\header}{
	XLII НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА\\
	Национален кръг, Варна, 13-16 март 2026 г.\\
	Група E, 4-5 клас, ден 2
}

В тази задача няма да се налага да определяте най-голям общ делител — Марти вече го е направил, макар и не съвсем точно.

Малкият Марти се забавлява със следната игра: написал е редица от $n$ цели положителни числа $a_1, a_2, \dots, a_n$ и започнал да търси най-дългата подредица от последователни числа, чийто НОД е по-голям от $1$. След известно време той с гордост съобщил, че търсеният НОД е число, равно на $k$. Никой не се съмнява в уменията на Марти да пресмята НОД, нито в това, че той понякога малко се разсейва... и е възможно числото $k$, което е определил като отговор, да не е съвсем точно. Освен това, улисан в пресмятането на НОД, той съвсем забравил колко е дълга търсената подредица.

Марти ви моли да напишете програма \texttt{nod}, която определя максималната дължина на подредица от последователни елементи с НОД по-голям от $1$ и  намира съответния НОД.

Гарантира се, че съществува точно една подредица с максимална дължина, за която $\mathrm{НОД} > 1$.

\subsection{Вход}
\vspace{0.1em}
От първия ред на стандартния вход се въвеждат  две  цели числа $n$ и $k$ — брой на елементите в редицата и НОД на търсената подредица с максимална дължина \textbf{според Марти}.  

От втория ред на стандартния вход се въвеждат $n$ цели положителни числа — елементите на редицата $a_1, a_2, \dots, a_n$. 

Числата са разделени с по един интервал.


\subsection{Изход}
\vspace{0.1em}
На единствения ред на стандартния изход програмата трябва да изведе две цели числа, разделени с интервал — максималната дължина на подредицата от последователни елементи с НОД по-голям от $1$ и НОД на тази подредица.


\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
    \item $2 \leq n \leq 2\ 000\ 000$.
    \item $0 < a_1, a_2, \dots, a_n \le 1\ 000\ 000$

    \item $2 \le k$; освен това $k$ се различава от търсения НОД с не повече от $50$.
     
\end{itemize}


%\newpage
\subsection{Оценяване}
\vspace{0.1em}
Задачата се оценява с $20$ теста. 
\begin{itemize}
    \item В $5$  теста $k$ е търсеният НОД.
    \item В $4$ теста $k$ се различава от търсения НОД с не повече от $2$.
    \item В $14$ теста $n \leq 500\ 000$.
\end{itemize}
\newpage
\subsection{Примери}
\begin{table}[H]
	\begin{tblr}{|l|l|X[j]|}
		\hline
		\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение на примера} \\
		\hline
		\texttt{\makecell[lt]{7 5\\
		2 10 5 15 3 14 14 
		}}
		& 
		\texttt{\makecell[lt]{3 5\\
		}}
		& 
		{
            Подредиците от последователни елементи с $\mathrm{НОД} > 1$ са: 
    $\{2, 10\}$, $\{10, 5, 15\}$, $\{15, 3\}$, $\{14, 14\}$. 
    Максималната дължина е $3$. 
    Марти съвсем точно е определил, че НОД е $5$.
		}
		\\
		\hline

        \texttt{\makecell[lt]{5 8\\
		1 6 12 6 30
		}}
		& 
		\texttt{\makecell[lt]{4 6\\
		}}
		& 
		{
            Марти малко се е разсеял и не е пресметнал съвсем точно най-големия общ делител.
		}
		\\
		\hline
	\end{tblr}
\end{table}
	
\end{document}