

Mountain ProblemA mountain range has the property that among its N elements there is an index M inside the range 1 < M < N, for which the sequence formed by the first M elements (a_{1}, a_{2}, …, a_{M}) is ascending and nonconstant, and the sequence consisting of the last N – M + 1 elements (a_{M}, a_{M + 1}, …, a_{N}) is descending and nonconstant. For example, the following 8 elements form a mountain range: {1, 1, 1, 2, 2, 2, 2, 1}. These sequences with N elements are indexed from 1 to N, the elements being a_{1}, a_{2}, …, a_{N}. These are signed 32bit integers, not necessarily distinct. We can apply two types of symmetric swap operations on these elements:
How many distinct mountain ranges can be achieved using any number of operations defined above? Example 1For N = 7 and a = {3,6,2,10,1,9,8}, we can obtain 4 distinct mountain ranges: The first mountain range can be obtained from the sequence {3,6,2,10,1,9,8} with the following operations:
The second mountain range obtained from {3,6,2,10,1,9,8} is:
The third mountain range obtained from {3,6,2,10,1,9,8} is:
The fourth mountain range obtained from {3,6,2,10,1,9,8} is:
Example 2For N = 8 and a = {2,1,2,1,1,1,2,2}, with the help of swap and double_swap operations, we can get 2 distinct mountain ranges: {1,1,1,2,2,2,2,1} and {1,2,2,2,2,1,1,1}, respectively. Input SpecificationThe input contains several sets of tests. Each test contains on its first line a number N, representing the length of the sequence (3 ≤ N ≤ 2005), and on the next line N natural numbers a_{i}, the elements of the mountain range (0 ≤ a_{i} ≤ 2 000 000 000), separated by a space. Output SpecificationPrint as many lines as there are sets of tests in the input. Each line should contain the results corresponding to the data in the input in the order in which they are read. For each read string, print the number of distinct mountain ranges that can be obtained by applying the swap and double_swap operations on the elements of the given ranges. As this value can be very high, the result should be printed in modulo 111 181 111. Note that each test case has at least one solution. Sample Input
Output for Sample Input
ExplanationFor the first test case, there are two solutions: {1,1,1,2,2,2,2,1} and {1,2,2,2,2,1,1,1}. For the second test case, there are four solutions: {2,3,6,10,9,8,1}, {2,8,9,10,6,3,1}, {1,8,9,10,6,3,2}, and {1,3,6,10,9,8,2}. For the third test case, there is only one solution: {1,2,1}. For the fourth test case, there are ten solutions: {1,1,1,1,1,1,2,100,2}, {1,1,1,1,1,1,100,2,2}, {1,1,1,1,1,2,2,100,1}, {1,1,1,1,1,2,100,2,1}, {1,1,1,1,1,100,2,2,1}, {1,2,2,100,1,1,1,1,1}, {1,2,100,2,1,1,1,1,1}, {1,100,2,2,1,1,1,1,1}, {2,2,100,1,1,1,1,1,1}, and {2,100,2,1,1,1,1,1,1}. 

University of Debrecen; Faculty of Informatics; v. 03/01/2019 