Вам задана перестановка \(p_1, p_2, \dots , p_n\) (перестановка — это массив, в котором все числа от \(1\) до \(n\) встречаются ровно один раз). Вес \(i\)-го элемента перестановки равен \(a_i\).
Сначала вы делите вашу перестановку на два непустых множества — префикс и суффикс. Более формально, первое множество содержит элементы \(p_1, p_2, \dots , p_k\), второе — \(p_{k+1}, p_{k+2}, \dots , p_n\), где \(1 \le k < n\).
После этого вы можете перемещать элементы между множествами. Точнее, вы можете выбрать элемент первого множества и переместить его во второе множество или наоборот. Вы заплатите \(a_i\) долларов за перемещение элемента \(p_i\).
Ваша задача — сделать так, чтобы любой элемент первого множества был меньше любого элемента второго множества. Обратите внимание, что если одно из множеств пусто, то это условие выполняется.
Например, если \(p = [3, 1, 2]\) и \(a = [7, 1, 4]\), то вам следует действовать следующим образом: разделить \(p\) на две части \([3, 1]\) и \([2]\), а затем переместить элемент, равный \(2\), в первое множество (это будет стоить \(4\)). А если \(p = [3, 5, 1, 6, 2, 4]\), \(a = [9, 1, 9, 9, 1, 9]\), то нужно делать так: разделить \(p\) на две части \([3, 5, 1]\) и \([6, 2, 4]\), а затем переместить элемент, равный \(2\), в первое множество (это стоит \(1\)), а элемент, равный \(5\) — во второе (это также стоит \(1\)).
Посчитайте минимальное количество долларов, которое вам придется потратить.