SPOJ in Armenian

Ամեն կիրակի Ալբերտը փորձում է լուծել Yerevan SU 1 թիմի շաբաթվա ընթացքում չլուծած խնդիրները։ Վերջերս Ալբերտը հանդիպել էր հետևյալ խնդրին։

Տրված է n հատ ամբողջ թվերից կազմված հաջորդականություն՝ a1, a2 …, an

Վերոնշյալ գործողությունը պետք է կիրառել այնքան մինչև որ ստացված հաջորդականությունը ունենա ճիշտ մեկ տարր։ Ձեր խնդիրն է կատարել գործողությունները այնպես, որ վերջնական տարրը լինի հնարավորինս մեծ։

Ալբերտին հաջողվել էր լուծել այս խնդիրը, հերթը ձերն է։

Մուտքային տվյալներ

Առաջին տողում տրված է  երկու աբողջ թիվ՝ n և f (f=0  կամ f=1):

Երկորդ տողում տրված է n հատ ամբողջ թիվ ,  |a[i]| <= 10^9:

Ելքային տվյալներ

Ելքի առաջին տողում պետք է արտածել վերջնական տարրի մեծագույն արժեքը։ Եթե f=0 ուրիշ ոչինչ արտածել պետք չէ։ Եթե f=1, ապա ելքի երկրորդ տողում անհրաժեշտ է արտածել կատարված գործողությունների քանակը, իսկ երրորդ տողում արտածել կատարված գործողությունները։

Ենթախնդիր 3

2 <= n <= 100000, f = 1

Օրինակ

Մուտք.
5 1
1 4 3 7 5

Ելք.
11
3
1 4 2

Օրինակի պարզաբանումը.
Առաջին գործողության ժամանակ կջնջենք առաջին տարրը և կստանանք {4, 3, 7 5}:
Երկորոդ գործողոթյան ժամանակ կջնջենք վերջին տարրը և կստանանք {4, 3, 7}:
Վերջին՝ երրորդ, գործողությամբ երկրորդ տարրը կփոխարինենք առաջին և երրոդ տարրերի գումարով,
այնուհետև կհեռացնենք առաջին և երրորդ տարրերը։
Արդյունքում կստանանք մեկ տարրից բաղկացած հաջորդականություն՝ {11}։