Nhân dịp lễ khai giảng năm học 2026-2027, trường THPT XYZ lên kế hoạch tổ chức cho học sinh đón chào đại biểu tham dự lễ.

Hiện tại thầy phụ trách đang sắp xếp ~n~ học sinh đứng thành một hàng ngang từ trái sang phải, học sinh thứ ~i~ mặc áo màu ~a_i~. Để hàng học sinh được đẹp mắt, thầy phụ trách cần điều chỉnh sao cho dãy màu áo của các học sinh tạo thành một dãy đối xứng. Một dãy được gọi là đối xứng nếu giống nhau khi đọc từ trái sang phải và từ phải sang trái. Ví dụ: dãy ~1,2,2,1~ là một dãy đối xứng trong khi dãy ~1,2,3,1~ thì không.

Để điều chỉnh, thầy phụ trách có thể thực hiện một số thao tác, mỗi thao tác sẽ thực hiện một trong hai công việc:

• Loại một học sinh bất kỳ ra khỏi hàng.

• Đổi màu áo của một học sinh bất kỳ trong hàng sang một màu khác.

Yêu cầu: Hãy giúp thầy phụ trách thực hiện ít thao tác nhất để dãy màu áo của các học sinh trong hàng trở thành dãy đối xứng, trong các phương án cùng thực hiện ít thao tác nhất, hãy đưa ra phương án sao cho độ dài dãy đối xứng là dài nhất.

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(1 \le n \le 3000)~.

• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1,a_2,\dots,a_n~ ~(1 \le a_i \le 3000)~ là số biểu thị màu áo của học sinh.

Output

• Dòng đầu ghi số nguyên ~x~ là số thao tác ít nhất cần thực hiện.

• Dòng thứ hai ghi số nguyên ~y~ là độ dài lớn nhất của dãy đối xứng tìm được khi thực hiện ~x~ thao tác.

Scoring

Sample Input 1

7
5 4 3 3 1 5 2

Sample Output 1

2
6

Notes

Một phương án tối ưu là: Đổi màu áo của học sinh thứ ~2~ thành màu ~1~, sau đó loại học sinh thứ ~7~ ra khỏi hàng. Lúc này màu áo của các học sinh trong hàng lần lượt là ~5,1,3,3,1,5~, đây là dãy đối xứng cần tìm.