导线问题

【题目描述】

哈蒙有$n$条导线排成一排，每条导线有一个电阻值，神奇的电光只能从一根导线传到电阻比它大的上面，而且必须从左边向右传导，当然导线不必是连续的。 哈蒙想知道电光最多能通过多少条导线，还想知道这样的方案有多少。

【输入】

第一行两个整数$n$和$type$。$type$表示数据类型。 第二行$n$个整数表示电阻。

【输出】

第一行一个整数表示电光最多能通过多少条导线。 如果$type=1$则需要输出第二行，表示方案数对$123456789$取模。

【输入样例】

5 1
1 3 2 5 4

【输出样例】

3
4

【提示】

【数据规模及约定】 对于20%的数据，$n≤10$。 对于40%的数据，$n≤1000$。 对于另外20%的数据，$type=0$。 对于另外20%的数据保证最多能通过不超过$100$条导线。 对于100%的数据$n≤100000$，电阻值不超过$100000$。