No submission language available for this problem.

Background

一年一度的仙门大比就要开始了，本次大比将会以闯练功房来进行积分制。一个练功房闯关成功，则加分，失败则减分。关小山因与练功房长老关系不错，因此获得了一张所有练功房的实力表。

Description

为了方便估算最终得分，关小山将加分减分的值，都以实力差值为准。比如关小山实力为 10，练功房实力 13，则战败，扣 3 分。又比如关小山实力为 10，练功房实力为 8，则战胜，加 2 分。

练功房按 1，2，3，4 ... n 编号顺序安排，参赛者可以从任意一个练功房开始闯，可以在任意编号往后的位置退出比赛，并拿着自己的积分参加积分榜。每位选手只有一次机会。

关小山能获得的最大积分值是多少？

注意，部分测试点还需要输出开始闯的位置和退出比赛的位置

Format

Input

第一行有 3 个整数 n，k，f 分别表示练功房的数量，关小山的实力和是否输出区间位置的标记。f 标志只是 0 和 1 。

第二行 n 个整数，按顺序表示练功房的实力值 $a_i$。

Output

第一行一个整数表示关小山在估算中能获得的最大积分值

若 f 为 1 则在第二行输出获得最大值时，开始闯关的位置和结束的位置。

Samples

7 8 0
6 12 5 9 6 10 5

4

7 8 1
6 12 5 9 6 10 5

4
3 5

Limitation

40% 保证 1 ≤ n ≤ 2×$10^3$

100% 保证 1 ≤ n ≤ 2×$10^5$ , 0 ≤ $a_i$ ≤ $10^4$