Tập Tam giác


Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 1000M

Author:
Problem type

Cho dãy số nguyên dương a1,a2,…,an từ dãy đã cho hãy chọn các phần tử tùy ý mỗi phần tử không quá 1 lần được 1 dãy mới nhiều phần tử nhất có thể sao cho lấy ra 3 giá trị bất kỳ có chỉ số khác nhau đều tạo thành 3 cạnh của tam giác.

Input

Dòng đầu chứa số nguyên dương n (1<n<=10^5)

Dòng thứ 2 chứa n số nguyên dương có giá trị không vượt quá 10^5

Output

Số phần được nhiều nhất sao cho lấy 3 giá trị bất kỳ có chỉ số khác nhau trong dãy đều là 3 cạnh tam giác. Trong trường hợp chỉ giữ lại được tối đa 2 phần tử thì in ra “Khong the tao ra day thoa man”

Ví dụ 1

Input

6
3 1 2 1 2 3

Output

4

Giải thích: Chọn ra dãy 3 2 2 3 gồm 4 phần tử thỏa mãn tính chất cứ chọn ra 3 số bất kỳ trong dãy này đều tạo thành 3 cạnh tam giác

Ví dụ 2

Input

6
2 3 1 5 9 16

Output

Khong the tao ra day thoa man
tichpx

Comments

There are no comments at the moment.