友情提示：380元/半年，儿童学编程，就上码丁实验室。
【题目描述】
哈蒙有$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$。