Soldiers

At the morning roll call in the barracks, every soldier stationed there must line up in a single row. They may not stand in an arbitrary order: they must stand sorted by height, from the tallest soldier to the shortest. The tallest soldier may stand at either end of the row, on the left or on the right. Help them count how many correct line-ups are possible.

Two line-ups are considered the same if and only if every soldier has the same neighbor on their left in both line-ups (or no left neighbor in both) and the same neighbor on their right in both line-ups (or no right neighbor in both).

Write a program that:

• reads the description of all soldiers in the barracks from standard input,
• computes the number of ways to line the soldiers up in one row sorted from the tallest to the shortest,
• prints the last four decimal digits of that number to standard output.

The first line contains one integer $n$ ($1 \le n \le 200\,000$), the number of soldiers in the barracks. The second line contains $n$ integers $w_i$ ($1 \le w_i \le 10^9$), separated by single spaces, giving the heights of the soldiers in input order.

Print, on the only line of output, the last four decimal digits of the number of ways to line the soldiers up in one row sorted by height. When that number is at least $1000$, print exactly four digits, padding with leading zeros if necessary. When it is smaller than $1000$, print all of its digits instead.

For the input with heights 2 3 1 4 4 5 2, all correct line-ups are listed below. Each entry shows a soldier's input index followed by that soldier's height in parentheses.

• 3 (1), 1 (2), 7 (2), 2 (3), 4 (4), 5 (4), 6 (5)
• 3 (1), 7 (2), 1 (2), 2 (3), 4 (4), 5 (4), 6 (5)
• 3 (1), 1 (2), 7 (2), 2 (3), 5 (4), 4 (4), 6 (5)
• 3 (1), 7 (2), 1 (2), 2 (3), 5 (4), 4 (4), 6 (5)
• 6 (5), 4 (4), 5 (4), 2 (3), 1 (2), 7 (2), 3 (1)
• 6 (5), 5 (4), 4 (4), 2 (3), 1 (2), 7 (2), 3 (1)
• 6 (5), 4 (4), 5 (4), 2 (3), 7 (2), 1 (2), 3 (1)
• 6 (5), 5 (4), 4 (4), 2 (3), 7 (2), 1 (2), 3 (1)

There are $8$ of them, which is why the answer for that input is $8$.