SPOJ in Armenian

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

Տրված է n հատ ամբողջ թվերից կազմված հաջորդականություն՝ a₁, a₂, …, a_n։ Հաջորդականության վրա հաջորդաբար պետք է կիրառել հետևյալ գործողությունը.

1. Ընտրել ընթացիկ հաջորդականության որևէ տարր։
2. Եթե ընտրված տարրը հաջորդականության եզրային տարր (առաջին կամ վերջին տարր) է, ապա հեռացնել այն, հակառակ դեպքում փոխարինել այն իր 2 հարևան տարրերի գումարով և հեռացնել այդ 2 հարևան տարրերը։
3. Ընթացիկ հաջորդականությունը փոխարինալ ստացված հաջորդականությամբ։

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

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

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

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

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

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

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

Ենթախնդիր 1

2 <= n <= 300, f = 0

Օրինակ

Մուտք.
5 0

1 4 3 7 5

Ելք.
11

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