Description

To defend against enemy missile attacks, a country developed a missile interception system. However, this system has a flaw: although the first shell can reach any height, each subsequent shell cannot be higher than the previous one. One day, the radar detected incoming enemy missiles. Since the system is still in the trial phase, there is only one set available, so it might not be able to intercept all missiles.

Given the heights of the incoming missiles in order, compute the maximum number of missiles this system can intercept, and the minimum number of such missile interception systems needed to intercept all missiles.

Input Format

One line containing several integers separated by spaces.

Output Format

Two lines, one integer per line. The first number is the maximum number of missiles this single system can intercept. The second number is the minimum number of such systems required to intercept all missiles.

389 207 155 300 299 170 158 65

6
2

Hint

For the first $50\%$ of the testdata (NOIP original testdata), the number of missiles does not exceed $10^4$. This part contributes $100$ points in total. An $\mathcal O(n^2)$ algorithm can pass.
For the remaining $50\%$ of the testdata, the number of missiles does not exceed $10^5$. This part also contributes $100$ points in total. Please use an $\mathcal O(n \log n)$ algorithm to pass.

For all testdata, missile heights are positive integers not exceeding $5 \times 10^4$.

In addition, this problem enables SPJ; there are two sub-questions per test point, and scoring is per sub-question.

NOIP 1999 Senior Problem 1.

$\text{upd 2022.8.24}$：A new hack testdata has been added.

Translated by ChatGPT 5