Сама задача конечно же довольно простая. Решив ее несколькими способами я каждый раз упирался в превышение объема допустимой памяти на 11 тесте. Соответственно львиная доля времени ушла на осознание того, что же именно потребляет память и на устранение этого узкого места.
Как можно было догадаться, память жрали Строки. Я убрал использование string отовсюду кроме считывания данных из консоли. Хранение данных реализовано через два массива int. Для разбора ввода и для вывода ответов в консоль использовались массивы int и char.

Вообще, это одна из тех задач, которые отлично иллюстрируют проблему, описанную в FAQ "Как писать решения на C#":
"В некоторых задачах потребуется собственная быстрая реализация разбора входных данных и форматирования выходных". Только здесь проблема не в скорости, а в памяти.