2004: 考试鄙视

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

第 1 行一个整数 N，表示考试的次数。

第 2 行 N 个整数，即 N 次考试的成绩。

输出共一行一个整数，这个学期所有考试的总共鄙视次数（总数可能很大，只需要输出总数 mod 123456 的值）。

4
1 3 3 5

3

【样例解释】第一次考试的分数是1，那么估计应该是第二次为2，第三次为3，第四次为4，但第二次实际分数为3，比2大，这是1次鄙视；第四次实际分数为5，比估计的4大，这也是2次鄙视；第二次考试的分数是3，那么估计应该是第三次为4，第四次为5，实际分数分别是3和5，所以没有鄙视；第三次考试的分数为3，那么估计第四次是4，但实际为5，这又是3次鄙视。因此总鄙视次数为3次。