Testing the CATCHER

1000ms    65536K
304    73
Easier

Description

A military contractor for the Department of Defense has just completed a series of preliminary tests for a new defensive missile called the CATCHER which is capable of intercepting multiple incoming offensive missiles. The CATCHER is supposed to be a remarkable defensive missile. It can move forward, laterally, and downward at very fast speeds, and it can intercept an offensive missile without being damaged. But it does have one major flaw. Although it can be fired to reach any initial elevation, it has no power to move higher than the last missile that it has intercepted.

The test which the contractor completed were computer simulations of battlefield and hostile attack conditions. Since they were only preliminary, the simulations tested only the CATCHER's vertical movement capability. In each simulation, the CATCHER was fired at a sequence of offensive missiles which were incoming at fixed time intervals. The only information available to the CATCHER for each incoming missile was its height at the point it could be intercepted and where it appeared in the sequence of missiles. Each incoming missile for a test run is represented in the sequence only once.

The General Accounting Office wants to be sure that the simulation test results submitted by the military contractor are attainable, given the constraints of the CATCHER. You must write a program that takes input data representing the pattern of incoming missiles and outputs the maximum numbers of missiles that the CATCHER can intercept for the test. Also if one CATCHER can not handle all incoming missiles what is the minimum number of the CATCHER by which can intercept all incoming missiles fot the test.

Input

The input data for any test consists of a sequence of one or more non-negative integers, all of which are less than or equal to 30,000, representing the heights of the incoming missiles (the test pattern).

Output

Output two intergers M and N.  M is the maximum number of incoming missiles that one CATCHER could possibly intercept for the test.  N is the minimum number of the CATCHER by which can intercept all incoming missiles fot the test.

Sample Input

300 250 275 252 200 138 245

Sample Output

5 2

Source

Editor

keefo on 2014-04-21 15:19:02