시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 64 20 20 32.258%

문제

세 숫자 x, y, z가 x+y>z, x+z>y, y+z>x의 관계를 만족하면, 세 수는 삼각관계에 있다고 한다.

마찬가지로 길이가 N인 수열 B(b[0], b[1], ..., b[n-1])의 모든 b[i], b[j], b[k]가 삼각관계에 있으면 이 수열은 삼각 수열이라고 한다. 이 때, i, j, k는 모두 다른 값이다.

수열 A가 주어졌을 때, 이 수열에서 적절히 몇 개의 원소를 빼서 ,이 수열을 삼각 수열로 만드려고 한다. 삼각 수열의 최대 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N이 주어진다. 둘째 줄에 수열 A에 들어있는 수가 공백을 사이에 두고 주어진다. N은 최대 50이고, A에 들어있는 수는 10^9보다 작거나 같은 자연수이다.

출력

첫째 줄에 가장 긴 부분 삼각 수열의 길이를 출력한다.

예제 입력

3
1 2 3

예제 출력

2

힌트

출처