F. CLC Loves SQRT Technology (Easy Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of the problem. The only difference between the two versions is the constraint on $$$n$$$.

You have an array of length $$$n$$$, We declare function $$$f(x)$$$ for a non-empty subsequence of the array as the minimum number of moves needed to change the subsequence's elements to make the subsequence $$$palindrome$$$. The move is defined as follows.

  • Select an element from the subsequence, and change the value to any arbitrary value.

Now your task is to find sum of $$$f(x)$$$ for all non-empty subsequences of the array.

Input

In the first line of input You'll be given number $$$n$$$ which shows the length of the array.

In the second line You'll receive the array.

$$$1 \le n \le 10^3$$$.

$$$1 \le a_i \le n$$$.

Output

Print an integer representing the sum of $$$f(x)$$$ for all non-empty subsequences, as the answer may be large, Print it modulo $$$998244353$$$.

Examples
Input
5
4 2 4 3 5
Output
30
Input
10
2 2 1 1 3 2 3 4 1 3
Output
1969
Input
5
2 5 3 1 4
Output
32