C. Chicken Jockey
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Welcome to the world of Minecraft! Made completely out of cubes. In here you met Steve, the architect of this world. Right now Steve is busy building a railway and you have decided to help him, being the selfless and helpful programmer you always are.

In particular he wants to build the railway on a straight line of $$$N$$$ cubes. But here the terrain is very messy, so every cube in the line may have a different elevation. In particular the first cube will have an elevation of $$$a_1$$$, the second cube will have an elevation of $$$a_2$$$, etc... up to $$$a_N$$$ for the elevation of the $$$N$$$-th cube.

In this Minecraft world a railway is made out of multiple, not necessarily connected, tracks. A track expands over a contiguous set of cubes of size at least $$$2$$$. No cube can be in more than one track, meaning no tracks ever intersect.

Because Steve is a really lazy guy, he wants to make sure his railway is planned to perfection before starting. He asks you to help him calculate the number of ways the railway can be made, with the added condition that a track has to start and end at the same elevation, because "You can only find Diamonds at the right level".

Since Steve is a considerate person it's not necessary to cover the $$$N$$$ cubes with tracks for a valid railway configuration. You can also decide not to create any track at all.

Input

On the first line a number $$$N$$$ ($$$1 \leq N \leq 3 \times 10^6$$$) the length of the line where the railway will be. On the second line $$$N$$$ numbers $$$a_1,a_2,...a_N$$$ ($$$1 \leq a_i \leq 10^5$$$) describing the elevation of each block in the line.

Output

Just one number, the ways the railway can be set. As this number can be very big, print it modulo $$$998244353$$$

Examples
Input
4
1 2 1 2
Output
3
Input
5
1 2 3 4 5
Output
1
Note

"And the universe said I love you because you are love."

For the first testcase the valid configurations are the following:

  • A track that starts on the first cube and ends on the third, both with elevation equal to $$$1$$$.
  • A track that starts on the second cube and ends on the fourth, both with elevation equal to $$$2$$$.
  • Building no tracks.

For the second testcase the only valid track configuration for the railway is to build no tracks at all.

This statement has been modified to include the clarifications made during the competition.