军训时需要排队形。假设队列中一共有n个人，任意两人身高不同，教官的排队方式如下：

1.所有人按任意顺序站成一排，作为初始队形。

2.从左到右依次安排每个人的位置，将人插入最终的队形中。

(1)第一个人直接进入队形中。

(2)从第二个人开始，如果他比前一个人高，就将其插入队形的最右边；否则，插入最左边。

已知教官最终得到的队形，超能侠想考考你，有多少种初始队形可以得到这个队形？请求出答案对12345取模的值。

输入文件第一行为一个整数n，表示队形中的人数。第二行为n个整数，每两个整数之间用一个空格隔开，代表最终得到的队形中每个人的身高。

输出文件包含一行一个整数，表示答案mod 12345的值。

对于40%的数据，保证 2≤n≤100；

对于100%的数据，保证 2≤n≤1000, 0≤身高≤2000。