问题描述

具体描述见教材p217： Whence这个学期考了n次试，每一次都有一个0~20000之间的整数分数。Whence本来的状态应该是每一次考试都比前一次多一分（除第一次），但由于他很不稳定，偏差可能很大。对于第i次考试，如果有第j次考试满足1<=j<i<=n, 且以第j次考试分数作为基准估计的第i次考试成绩比实际成绩低， 就说第i次考试鄙视了第j次考试(估计分可以超过20000)。为了提高自信，Whence想知道他这个学期所有考试总共有多少次鄙视。

格式

输入

第1行n(1<n<=100000)。 第2行为n次考试成绩。

输出

1行，这个学期所有考试的总共鄙视次数（总数可能很大，只需要输出总数 mod12345的值）。 样例说明：第一次考试的分数是1。那么估计应该是第二次为2，第三次为3，第四次为4，但第二次实际分数为3，比2大，这是1次鄙视； 第四次实际分为5，比估计的4大，这也是1次鄙视；第二次考试的分数是3，那么估计应该是第三次为4，第四次为5，实际分数分别是3和5，所以没有鄙视；第三次考试的分数为3，那么估计第四次是4，但实际为5，这又是1次鄙视。因此总鄙视次数为3次。

样例

4
1 3 3 5

3

限制

1s, 64MB.