D. Three Subsegments
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an integer array $$$a_1, a_2, \dots, a_n$$$, all numbers in the array in range from $$$1$$$ to $$$m$$$.

Count the number of ways to choose three non-empty, non-overlapping subsegments such that the number of occurrences of each number from $$$1$$$ to $$$m$$$ in the union of these three subsegments is the same even number.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 300; 1 \le m \le n$$$) — the size of the array and the maximum possible value in it.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le m$$$) — the array $$$a$$$.

Output

In a single line, print the answer to the problem — the number of ways to choose three non-empty, non-overlapping subsegments such that the number of occurrences of each number from $$$1$$$ to $$$m$$$ in the union of these three subarrays is the same even number.

Examples
Input
5 2
2 1 2 2 1
Output
7
Input
12 3
1 2 3 2 1 3 3 1 1 2 3 2
Output
278
Note

In the first test, all valid unions look like this:

  • [2] [1] 2 [2 1];
  • [2] [1 2] 2 [1];
  • [2 1] [2] 2 [1];
  • [2 1] 2 [2] [1];
  • 2 [1] [2] [2 1];
  • 2 [1] [2 2] [1];
  • 2 [1 2] [2] [1];

For the second test, there are only some of the valid unions:

  • [1 2 3 2] [1 3 3 1 1 2] [3 2];
  • 1 2 [3 2] 1 [3] 3 [1 1 2] 3 2;
  • [1 2 3] 2 1 3 [3 1] 1 2 3 [2];
  • [1] [2 3 2] [1 3] 3 1 1 2 3 2;
  • [1] 2 3 2 1 3 [3 1] 1 [2 3 2];
  • 1 [2 3] [2 1 3] 3 1 [1] 2 3 2;