삼각형 막대

시간 제한1초메모리 제한512 MB

요약

길이가 1부터 500까지인 막대 최대 30000개에서 어느 세 개를 골라도 삼각형이 되는 가장 큰 부분집합을 구합니다.

난이도: 보통10점 중 6점
유형: 정렬, 완전 탐색, 누적 합
정답자: 아직 제출이 없습니다

문제

Jaś는 막대로 삼각형 만들기를 좋아합니다. 막대들을 주머니에 넣어 두고 그 안에서 세 개를 아무렇게나 꺼냅니다. 막대들의 길이가 서로 다르기 때문에 꺼낸 세 막대로 항상 삼각형을 만들 수 있는 것은 아니고, 만들 수 없을 때마다 Jaś는 크게 짜증을 냅니다. 이를 막기 위해, 주머니에 남은 막대들 중 어느 세 개를 골라도 삼각형을 만들 수 있도록 일부 막대를 버리려고 합니다. 단, 주머니에는 되도록 많은 막대를 남겨야 합니다.

길이가 $a$ , $b$ , $c$ 인 세 막대는 어느 두 길이의 합이 나머지 한 길이보다 클 때 삼각형을 이룹니다. 즉 $a \le b \le c$ 이면 $a + b > c$ 일 때에만 삼각형이 됩니다. (한 직선 위에 놓이는 납작한 경우는 삼각형으로 치지 않습니다.)

다음을 수행하는 프로그램을 작성하세요.

주머니에 있는 막대의 개수와 각 막대의 길이를 입력받고,
남긴 막대들 중 어느 세 개를 골라도 삼각형을 이루도록 남길 수 있는 막대의 최대 개수를 구하여,
그 값을 출력합니다.

입력

첫째 줄에 주머니에 있는 막대의 개수 $N$ ( $5 \le N \le 30\,000$ )이 주어집니다. 다음 $N$ 개의 줄에는 각각 막대 하나의 길이가 주어지며, 길이는 $1$ 이상 $500$ 이하의 정수입니다.

출력

어느 세 개를 골라도 삼각형을 이루도록 주머니에 남길 수 있는 막대의 최대 개수를 한 줄에 출력합니다.

예제1

예제 1
입력
```
10
7
1
2
8
10
6
1
7
9
9
```
예상 출력
```
7
```