Gats and the Flipped Garland

Time limit: 2000 msMemory limit: 256 MB

Gats has arranged $N$ colored beads in a line. The color of the bead at position $i$ is $C_i$ .

He chooses one pair of indices $(L,R)$ uniformly at random from all pairs satisfying $1\le L\le R\le N$ . He then reverses the order of the beads from position $L$ through position $R$ , inclusive. Let the resulting sequence of colors be $B_1,B_2,\ldots,B_N$ .

Each gap between adjacent positions has a different sensitivity. For every $i$ satisfying $1\le i<N$ , the gap between positions $i$ and $i+1$ contributes tension units if , and contributes otherwise. Thus the total tension is

T(B)=\sum_{i=1}^{N-1} i\cdot \mathbf{1}[B_i\neq B_{i+1}].

Find the expected total tension after Gats performs the random reversal.

Input

The first line contains an integer $N$ ( $1\le N\le 2\cdot 10^5$ ), the number of beads.

The second line contains $N$ integers (), the colors of the beads in their initial order.

Output

Let $P=998244353$ , and let $S$ be the sum of the resulting tensions over all $M=N(N+1)/2$ possible intervals.

Print the integer

Samples

Sample 1

Input

1
7

Output

There is no gap between beads, so the tension is always $0$ .

Sample 2

Input

3
1 2 2

Output

499122178

For intervals $[1,1]$ , $[2,2]$ , $[3,3]$ , , , and , the resulting tensions are , and . Their expected value is , whose required representation is .

Gats and the Flipped Garland

Input

Output

Samples

Sample 1

Sample 2

Submit

Submissions