E. Мороженое
Задачу добавил: alef
Успешно сдано решений: 89
Танцевальный марафон окончился, и организаторы подводят итоги. А пока идёт подсчёт, всех участников пригласили на танцпол, попросили выстроиться в ряд и вручили каждому по мороженому.
Про каждого участника известно, какое мороженое он получил и какое мороженое он больше всего любит. Т.е., участник #j получил мороженое сорта sj, при этом больше всего он любит мороженое сорта mj. Также известно, что чем меньше разность 
, тем более довольным будет участник.
Конечно, некоторые участники заметили, что мороженое, которое досталось другим участникам, нравится им больше, чем то, которое досталось им. И предложили устроить обмен.
Поскольку день жаркий, и мороженое может быстро растаять, каждый участник может поменяться своим мороженым только один раз. А поскольку организаторы просят участников сохранять ряд, участник может поменяться своим мороженым только с непосредственным соседом слева или с непосредственным соседом справа (конечно, если таковые есть).
Ваша задача — составить план обменов так, чтобы минимизировать недовольство самого недовольного мороженым участника.
В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество участников в ряду.
Во второй строке содержится n целых чисел s1, s2, ..., sn (1 ≤ sj ≤ 105, j = 1, 2, ..., n) — сорта мороженого, которые были выданы участникам; sj выдан участнику #j.
В третьей строке содержится n целых чисел m1, m2, ..., mn (1 ≤ mj ≤ 105, j = 1, 2, ..., n) — сорта мороженого, которые более всего любят участники; mj является наиболее любимым сортом участника #j.
В первой строке выведите минимально возможное недовольство самого недовольного участника.
Во второй строке выведите n чисел через пробел. На позиции #i выведите либо собственно число i, если участник не будет ни с кем меняться мороженым, либо номер участника, с которым участник #i должен поменяться мороженым.
Если существует несколько возможных планов обменов, выведите любой.
Подзадача 1 (до 20 баллов)
1 ≤ n ≤ 15
Баллы начисляются за каждый пройденный тест, по запросу сообщаются результаты проверки на каждом тесте.
Подзадача 2 (до 80 баллов)
Входные данные могут принимать любые допустимые значения.
Баллы начисляются в случае прохождения всех тестов группы.
По запросу сообщается номер первого непройденного теста в группе
3
3 4 5
4 5 3
1
1 3 2
Рассмотрим приведённый пример.
Могло быть три варианта развития событий:
- никто ни с кем не менялся. Тогда недовольства участников равны соответственно
, и самый недовольный имеет недовольство 2. - участники #1 и #2 обменялись мороженым. В этом случае недовольства участников равны
. Наиболее недовольный участник имеет недовольство 2, как и в предыдущем случае. Хотя теперь таких максимально недовольных уже двое. - участники #2 и #3 обменялись мороженым. Недовольства участников будут такими:
. В этом случае недовольство самого недовольного участника окажется равным 1. Именно такой способ обмена и следует выбрать.