Counting Valid Initial Permutations for Choir Formation

In this problem, you have a choir of (n) people with distinct heights (h_i) (where (1000 \le h_i \le 2000)). They are arranged in a final lineup (ideal formation) via the following process:

1. The very first person in an initial order is inserted into an empty formation.
2. Then, for each subsequent person (in the order they appear in the initial permutation), compare their height with the height of the person immediately before them in the initial order:
   • If the current person is taller (i.e. (h_{current} > h_{previous})), they are appended to the right end of the formation.
   • Otherwise (i.e. (h_{current} < h_{previous})), they are inserted at the left end of the formation.

After all (n) people have been inserted, the resulting formation is obtained.

For example, if the initial order of 6 people is:

1850, 1900, 1700, 1650, 1800, 1750,

the insertion process is as follows:

• Start: [1850]
• 1900 ((1900 > 1850)) (\to) [1850, 1900]
• 1700 ((1700 < 1900)) (\to) [1700, 1850, 1900]
• 1650 ((1650 < 1700)) (\to) [1650, 1700, 1850, 1900]
• 1800 ((1800 > 1650)) (\to) [1650, 1700, 1850, 1900, 1800]
• 1750 ((1750 < 1800)) (\to) [1750, 1650, 1700, 1850, 1900, 1800]

Thus the final formation is: 1750, 1650, 1700, 1850, 1900, 1800.

Your task is: given the ideal final formation (a permutation of the (n) distinct heights), determine how many initial orders (permutations) would produce exactly this final formation when using the above insertion algorithm. Since the answer can be very large, output it modulo (19650827).

A hint for reconstruction:

If we denote the final formation as (F = [f_1, f_2, \dots, f_n]) (from left to right), note that the first person in the initial order, say (p_1), must appear at position (k+1) in (F) where (k) is the number of people inserted at the left end. The left inserted persons appear in (F[1 \dots k]) (in reverse of their insertion order) and the right inserted persons appear in (F[k+2 \dots n]) (in the same order as their insertion).

The problem then reduces to counting the number of interleavings of the two fixed subsequences (derived from (F)) that maintain the required inequality conditions at every insertion step:

• For an insertion from the left subsequence, the person must be shorter than the previously inserted person.
• For an insertion from the right subsequence, the person must be taller than the previously inserted person.

Solve this problem for all possible choices of (k) (with (0 \le k \le n-1)) and output the total count modulo (19650827).

inputFormat

The first line contains a single integer (n) (the number of people).
The second line contains (n) space‐separated integers, representing the heights of the choir members in the final formation from left to right.

outputFormat

Output a single integer — the number of valid initial orders that produce the given final formation, taken modulo (19650827).

sample

6
1750 1650 1700 1850 1900 1800

1