Longest Palindromic Subsequence

You are given an integer n and a sequence of n integers. Your task is to find the length of the longest palindromic subsequence within the given sequence.

A palindromic subsequence is a sequence that reads the same forward and backward. The subsequence is not required to be contiguous.

The solution to this problem typically involves dynamic programming with a time complexity of \(O(n^2)\). You need to design your solution in such a way that it reads input from stdin and writes the result to stdout.

inputFormat

The input is given via standard input (stdin) and consists of two lines:

• The first line contains a single integer n which represents the length of the sequence.
• The second line contains n space-separated integers representing the sequence.

outputFormat

Output a single integer that denotes the length of the longest palindromic subsequence in the sequence. The output should be printed to standard output (stdout).

5
1 2 3 2 1

5