% !TeX program=lualatex

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

\begin{document}
	
\renewcommand{\tl}{$0.3$ сек.}
\renewcommand{\ml}{$256$ MB}
\problem{Задача CT2. ПРЕМАХВАНЕ}
\renewcommand{\header}{
	ТРЕНИРОВКА\\
	Група C – 7, 8 клас
}

Яна наскоро се сдоби с чисто нова пермутация $p_1, p_2, \dots p_n$ на естествените числа от $1$ до $n$. Тя се чуди как да убива времето с нея и решава да извършва следната операция няколко (а може и николко) пъти: тя ще избере два съседни елемента в пермутацията и ще премахне този с по-голяма стойност. Много любопитно на Яна се струва да разбере колко различни редици може да получи от първоначалната си пермутация по този начин.

Напишете програма \textbf{\texttt{removal.cpp}}, която да помогне на Яна да разреши своя казус. Понеже отговорът може да се окаже твърде голям, тя ще се задоволи да научи остатъкът му при деление на $10^9 + 7$. 

\subsection{Вход}

На първия ред на стандартния вход се въвежда $n$ -- броя елементи в пермутацията. На следващия ред на стандартния вход ще се въведат $n$ числа, които описват числата в началната редица. Забележете, че всяко число от $1$ до $n$ се среща в редицата и то точно веднъж.

\subsection{Изход}

На единствения ред на стандартния изход изведете единствено число, представляващо броя различни редици, които Яна може да получи по модул $10^9+7$.

\subsection{Ограничения}
\begin{itemize}
	\item $1 \le n \le 300~000$
	\item $1 \le a_i \le n$
	\item Всяко число от $1$ до $n$ се среща точно веднъж в редицата.
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \makecell{\textbf{Необходими} \\ \textbf{подзадачи}} & \textbf{Други ограничения} \\
        \hline
        	$0$ & $ 0$ & $ - $ & Примерните тестове.\\ 
        \hline
        	$1$ & $20$ & $ 0 $ & $n \le 200$\\ 
		\hline
			$2$ & $13$ & $ - $ & $n \le 2000, a_i = i$\\ 
		\hline
			$3$ & $17$ & $ 2 $ & $a_i = i$\\ 
		\hline
			$4$ & $23$ & $1,2$ & $n \le 2000$\\ 
		\hline
			$5$ & $27$ & $0-4$ & Няма.\\ 
		\hline
    \end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея.}
\end{table}

\subsection{Пример}
\begin{table}[H]
	\begin{tblr}{|X[30,l]|X[20,l]||X[30,l]|X[20,l]|}
		\hline
		\textbf{Вход 1} & \textbf{Изход 1} & \textbf{Вход 2} & \textbf{Изход 2}  \\
		\hline
		\texttt{3\\2 3 1} & \texttt{3} &
		\texttt{4\\2 1 4 3} & \texttt{6} \\
		\hline
	\end{tblr}
\end{table}

\pagebreak

\subsection{Обяснение на примерите}

От пермутацията на първия пример можем да получим редиците $[2,3,1], [2,1]$ и $[1]$.

От пермутацията на втория пример можем да получим редиците $[2,1,4,3], [1,4,3], [1,3], [1], [2,1,3], [2,1]$.

\end{document}
