Missile Interception and Defense Systems

A country has developed a missile interception system to defend against enemy missile attacks. However, the system has a flaw: although the first projectile can reach any height, each subsequent projectile cannot exceed the height of the previous one. Given a sequence of incoming missile heights, your task is twofold:

• Determine the maximum number of missiles that one interception system can intercept. In a valid interception sequence of missiles with heights \(h_1, h_2, \dots, h_k\), the following condition must hold: \[ h_1 \ge h_2 \ge \cdots \ge h_k \]
• If you want to intercept all missiles, compute the minimum number of interception systems required. This is equivalent to partitioning the missile sequence into the minimum number of non-increasing subsequences. By Dilworth's Theorem, this number is equal to the length of the longest strictly increasing subsequence, i.e., \[ \max \{k : h_{i_1} < h_{i_2} < \cdots < h_{i_k} \} \]

Note: The first missile intercepted by any system is free to choose any height.

inputFormat

The input begins with a positive integer N (\(1 \le N \le 10^3\)), representing the number of incoming missiles. The following N lines each contain one integer, representing the height of each missile in the order of arrival.

outputFormat

Output two space‐separated integers on a single line. The first integer is the maximum number of missiles that can be intercepted by one system, and the second integer is the minimum number of systems required to intercept all missiles.

sample

8
389
207
155
300
299
170
158
65

6 2