題目描述

有一個長度為 n 的數列 a，請你求出它的最長回文子序列的長度。

回文的序列就是從前往後讀和從後往前讀結果一樣的序列。

[1 2 1]、[1 13 13 1] 是回文的，而 [1 14 5] 不是回文的。

子序列即是從一個序列中取部分元素按照原順序排成的新序列。

[1 1 4]、[1 4 5]、[1 4 1] 都是 [1 1 4 5 1 4] 的子序列，而 [5 4 1]、[1 1 1 5] 不是。

輸入格式

n

a[1] a[2] . . . a[n]

輸出格式

ans

Samples

["6\r\n1 1 4 5 1 4","7\r\n1 2 3 4 3 2 1","5\r\n1 2 3 4 5"]

["3","7","1"]

提示

約束條件

• 1 ≤ n ≤ 100000
• ∀1 ≤ i ≤ n, 1 ≤ a[i] ≤ 10¹⁸
• ∀1 ≤ x ≤ 10¹⁸，x 在 a 中出現的次數不超過 20。

子任務

1. （10分）n ≤ 15
2. （40分）n ≤ 1000
3. （50分）没有額外的約束條件。

原始資料

• Zero1 題號：b341
• Hydro 題號：Z1341
• Locale：zh_TW
• Display：practice