URI Online Judge | 2976

Triangles

By Mladen Radojević RS Serbia

Timelimit: 2

You are given an array of positive integers. Find the maximal substring (i.e. a subset of at least three consecutive elements of the array) so that any three distinct elements from that substring can form the sides of a triangle. Also, find the maximal subsequence (a subset consisting of at least three elements, not necessarily consecutive) with the same property.

Input

The first line of input contains one integer N (1 ≤ ≤ 100,000), the number of elements in the array. The next N lines contain the elements of the array (elements of the array are positive integers, each less than or equal to 109).

Output

Output consists of exactly two lines, each containing one integer– the length of the maximal substring and the maximal subsequence with the property described above, respectively. If such substring or subsequence doesn’t exist, the corresponding value is zero.

Input Sample Output Sample

5

60

30

20

40

60

3

4