Triangle Subsequence

Interview

Time limit2sMemory limit128 MB

Summary

Given a sequence, find the longest subsequence where every triple of elements satisfies the triangle inequality.

Level: Medium5 of 10
Topics: Sorting, Two pointers, Greedy
Solved: No attempts yet

Problem

Three numbers x, y, and z are said to be in a triangle relation if all of x + y > z, x + z > y, and y + z > x hold.

For a sequence B of length N, if B[i], B[j], and B[k] are in a triangle relation for every choice of three distinct positions i, j, and k, then B is called a triangle sequence.

You are given a sequence A. Delete any number of elements from A so that the remaining sequence is a triangle sequence. Find the maximum possible length of such a sequence.

Input

The first line contains the size N of the sequence.

The second line contains the elements of sequence A, separated by spaces. N is a positive integer at most 50, and each element of A is a positive integer at most 10^9.

Output

Print the length of the longest possible triangle subsequence.

Examples5

Example 1
Input
```
3
1 2 3
```
Expected output
```
2
```
Example 2
Input
```
7
2 3 4 1 3 4 5
```
Expected output
```
5
```
Example 3
Input
```
8
1 1 1 1 1 1 1 1
```
Expected output
```
8
```

Example 4

Input

6
1 1 1 1000000000 1000000000 1000000000

Expected output

Example 5
Input
```
1
1000000000
```
Expected output
```
1
```