Hi, please write an efficient program in C to solve the following problem (given as LaTeX source):

Ivan is playing a card game with $n$ cards. Each card has an integer written on it. The cards have just been shuffled, and are now lying in a row.

Ivan has a red marker, with which he can make cards red. Initially, none of the cards are red. In the current step of Ivan's game, he must mark a subset of the cards red, as follows:
\begin{itemize}
    \item Whenever a red-marked card $c_1$ lies to the left of another red-marked card $c_2$ (possibly with other cards in between), the number written on $c_1$ must not be greater than the number written on $c_2$.
	\item The number of red-marked cards must be the highest amount that is possible while following the rule above.
	\item If there are still multiple possible ways to mark the cards while following the two rules given above, then out of all options, Ivan must choose the \textit{lexicographically smallest} option: that is, the number on the first red-marked card (from the left) must be the smallest. After that, the number on the second red-marked card must be the smallest, and so on.
    \item Under the constraints given above, if there are still several possible ways to mark the cards, Ivan chooses one of them arbitrarily.
\end{itemize}

After Ivan has marked the cards,
his \textit{red-score} is defined as the difference between the number on the rightmost red card and the number on the leftmost red card.

What is the number of cards that Ivan will mark red, and what will be his red-score?

\subsection*{Input and output}
The first line of the input contains the number $n$, the number of cards. The next line contains the numbers written on the $n$ cards, in the order in which the cards are lying on the table.

This is an example input:
\begin{lstlisting}
11
4 3 5 4 8 12 6 27 33 29 5
\end{lstlisting}

In this case, Ivan will mark six cards red, in the following way:\\
\texttt{
	\textcolor{gray!70!white}{4}
	\textcolor{red}{\textbf{\underline3}}
	\textcolor{gray!70!white}{5}
	\textcolor{red}{\textbf{\underline4}}
	\textcolor{red}{\textbf{\underline8}}
    \textcolor{red}{\textbf{\underline{12}}}
	\textcolor{gray!70!white}{6}
    \textcolor{red}{\textbf{\underline{27}}}
	\textcolor{gray!70!white}{33}
    \textcolor{red}{\textbf{\underline{29}}}
	\textcolor{gray!70!white}{5}}\,.

In this case, Ivan's red-score is $29-3=26$.

\begin{minipage}{\textwidth}
Notice that there would also have been other ways to mark six cards red, for example like this:\\
\texttt{
	\textcolor{gray!70!white}{4}
    \textcolor{red}{\textbf{\underline3}}
    \textcolor{red}{\textbf{\underline5}}
	\textcolor{gray!70!white}{4}
	\textcolor{red}{\textbf{\underline8}}
    \textcolor{red}{\textbf{\underline{12}}}
	\textcolor{gray!70!white}{6}
    \textcolor{red}{\textbf{\underline{27}}}
	\textcolor{gray!70!white}{33}
    \textcolor{red}{\textbf{\underline{29}}}
	\textcolor{gray!70!white}{5}}\,, or\\
\texttt{
    \textcolor{red}{\textbf{\underline4}}
	\textcolor{gray!70!white}{3}
    \textcolor{red}{\textbf{\underline5}}
	\textcolor{gray!70!white}{4}
	\textcolor{red}{\textbf{\underline8}}
    \textcolor{red}{\textbf{\underline{12}}}
	\textcolor{gray!70!white}{6}
    \textcolor{red}{\textbf{\underline{27}}}
	\textcolor{gray!70!white}{33}
    \textcolor{red}{\textbf{\underline{29}}}
	\textcolor{gray!70!white}{5}}\,, or\\
\texttt{
	\textcolor{gray!70!white}{4}
	\textcolor{red}{\textbf{\underline3}}
	\textcolor{gray!70!white}{5}
	\textcolor{red}{\textbf{\underline4}}
	\textcolor{red}{\textbf{\underline8}}
    \textcolor{red}{\textbf{\underline{12}}}
	\textcolor{gray!70!white}{6}
    \textcolor{red}{\textbf{\underline{27}}}
    \textcolor{red}{\textbf{\underline{33}}}
	\textcolor{gray!70!white}{29}
	\textcolor{gray!70!white}{5}}\,.
\end{minipage}

However, all of these alternative options are invalid, because the sequence of numbers on the red cards is not the lexicographically smallest possibility. The sequence $(3,4,8,12,27,29)$ is lexicographically smaller than $(3,5,8,12,27,29)$, $(4,5,8,12,27,29)$ and $(3,4,8,12,27,33)$. Ivan always chooses the lexicographically smallest possibility, which is the very first one shown above.

You must output the number of cards that Ivan will mark red, and his red-score:
\begin{lstlisting}
6 26
\end{lstlisting}

\begin{minipage}{\textwidth}
\subsection*{Constraints}
\begin{itemize}
	\item In all test cases, $1\leq n\leq 4\,000\,000$.
	\item The numbers written on the cards can lie between $-10^8$ and $10^8$, inclusive.
    \item CPU time limit: 2 seconds per test case.
    \item Memory limit: 256 MiB per test case.
\end{itemize}
\end{minipage}