Сегодня вам предстоит прослушать n лекций, на i-й лекции вы можете получить ai знаний.
Чтобы увеличить эффект от учебы, перед лекцией вы можете помедитировать — в таком случае за эту лекцию вы получите удвоенное количество знаний.
К сожалению, вы не можете медитировать перед двумя лекциями подряд — эффект сильно ослабнет.
Вычислите наибольшее количество знаний, которое вы можете получить за все лекции, медитируя в оптимальные моменты времени.
В первой строке содержится целое число n 
— количество лекций.
Во второй строке содержится n целых чисел a1, a2, ..., an 
— количество знаний, которое вы получите по умолчанию за j-ю лекцию.
В первой строке выведите целое число k — максимально возможное суммарное количество знаний, которое вы можете получить за день.
Во второй строке выведите n символов s1s2... sn, где символ sj = M, если вы медитировали перед j-й лекцией, и sj = O, если вы слушали лекцию без медитации.
Символы M и O — заглавные латинские буквы.
Если существует несколько вариантов ответа с оптимальным количеством знаний, выведите любой.
6
1 8 1 1 5 2
31
OMOOMO
7
2 4 2 3 5 4 5
39
MOMOMOM
Первый тестовый пример
Вы решили помедитировать перед 2-й и 5-й лекциями — суммарно получили 1 + 8·2 + 1 + 1 + 5·2 + 2 = 31.
Второй тестовый пример
В данном случае вы медитировали перед каждой нечетной лекцией — суммарно получилось 2·2 + 4 + 2·2 + 3 + 5·2 + 4 + 5·2 = 39.
Обратите внимание, что вы не могли, например, медитировать и перед 5-й, и перед 6-й лекциями.
