Cho dãy số $A_1,A_2,\ldots,A_n$ có $n$ phần tử nguyên dương. Hãy tìm dãy con dài nhất (có thể các phần tử không liên tiếp) của dãy sao cho ba số nguyên bất kỳ trong dãy đều có thể là ba cạnh của tam giác.

Input

Đọc từ file văn bản TRISEQ.INP có cấu trúc như sau:

• Dòng thứ nhất chứa số nguyên dương $n$;
• Dòng thứ hai chứa $n$ số nguyên dương $A_1,A_2,\ldots,A_n$.

Output

Ghi ra file văn bản TRISEQ.OUT một số nguyên dương là độ dài lớn nhất của dãy con tìm được. Dữ liệu luôn đảm bảo đáp án từ $3$ trở lên.

Scoring

• Subtask 1 ($30\%$): $0<n \leq 15$;
• Subtask 2 ($40\%$): $15 < n \leq 1000$;
• Subtask 3 ($100\%$): $1000 < n \leq 10^6$.

Example

5
1 2 3 4 5

3