Woburn Challenge 2017-18 Round 2 - Senior Division

Having walked many a mile over the course of their journey, and with the last of their strength just about depleted, Frodo and Sam have at last changed their mind about the whole "walking into Mordor to throw the Ring into Mount Doom" plan. It really does seem rather dangerous! Fortunately, they've devised an alternate strategy to destroy the One Ring, thereby saving Middle Earth from Sauron's impending rule.

The Ring is a circle-shaped object with ~N~ ~(3 \le N \le 400)~ evenly-spaced markings inscribed on it. Numbering the markings in clockwise order, the ~i^{th}~ marking is an inscription of the integer ~L_i~ ~(1 \le L_i \le 10^9)~ in Sauron's Black Speech. For the sake of science, we can consider the ring to be arbitrarily thin (a circle on a plane, when viewed from above), and the markings to be arbitrarily small (points on that circle).

The Ring is normally resistant to simply being cut into pieces with a sword, but Frodo and Sam have realized the secret behind its power. They're going to simultaneously make one or more precise cuts through it. Each cut can be thought of as a line segment intersecting the circle at two points. No cut may pass directly through any of the Ring's markings.

The Ring is only able to keep itself together if there exists at least one pair of markings ~i~ and ~j~, such that ~L_i \ne L_j~ and none of the cuts intersect the line segment connecting those two markings. As such, Frodo and Sam hope to perform their cuts so as to interrupt the power of all of these pairs of markings, thus destroying the Ring.

Performing many cuts simultaneously is a difficult task for a pair of Hobbits, so they'd like to minimize the number of cuts. There's just one detail they can't decide on: Frodo is confident that they'll be able to execute any set of cuts they'd like to, while Sam is concerned that it'll only be doable if none of the cuts' line segments intersect with one another.

So, let's consider two different cases - either any set of possibly-intersecting cuts may be made, or the cuts must all be non-intersecting. For each case, determine the minimum number of cuts which must be made in order for the Ring to be destroyed. At least one cut is guaranteed to be required (in other words, the integers ~L_{1 \dots N}~ will not all be equal).

Subtasks

In test cases worth ~6/37~ of the points, ~N \le 15~.
In test cases worth another ~16/37~ of the points, ~N \le 50~.

Input Specification

The first line of input consists of a single integer ~N~.
The next line consists of integers ~L_{1 \dots N}~.

Output Specification

Output two space-separated integers, the minimum number of cuts which must be made with and without them being allowed to intersect, respectively.

Sample Input

8
1 2 4 4 1 1 3 2

Sample Output

3 4

Sample Explanation

The below two diagrams illustrate sample ways in which the ring can be destroyed with as few cuts as possible, with and without the cuts being allowed to intersect: