{"raw_statement":[{"iden":"problem statement","content":"You are given a permutation $p = (p_1, \\ldots, p_N)$ of ${ 1, \\ldots, N }$. You can perform the following two kinds of operations repeatedly in any order:\n\n*   Pay a cost $A$. Choose integers $l$ and $r$ ($1 \\leq l < r \\leq N$), and shift $(p_l, \\ldots, p_r)$ to the left by one. That is, replace $p_l, p_{l + 1}, \\ldots, p_{r - 1}, p_r$ with $p_{l + 1}, p_{l + 2}, \\ldots, p_r, p_l$, respectively.\n*   Pay a cost $B$. Choose integers $l$ and $r$ ($1 \\leq l < r \\leq N$), and shift $(p_l, \\ldots, p_r)$ to the right by one. That is, replace $p_l, p_{l + 1}, \\ldots, p_{r - 1}, p_r$ with $p_r, p_l, \\ldots, p_{r - 2}, p_{r - 1}$, respectively.\n\nFind the minimum total cost required to sort $p$ in ascending order."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $1 \\leq N \\leq 5000$\n*   $1 \\leq A, B \\leq 10^9$\n*   $(p_1 \\ldots, p_N)$ is a permutation of ${ 1, \\ldots, N }$."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $A$ $B$\n$p_1$ $\\cdots$ $p_N$"},{"iden":"sample input 1","content":"3 20 30\n3 1 2"},{"iden":"sample output 1","content":"20\n\nShifting $(p_1, p_2, p_3)$ to the left by one results in $p = (1, 2, 3)$."},{"iden":"sample input 2","content":"4 20 30\n4 2 3 1"},{"iden":"sample output 2","content":"50\n\nOne possible sequence of operations is as follows:\n\n*   Shift $(p_1, p_2, p_3, p_4)$ to the left by one. Now we have $p = (2, 3, 1, 4)$.\n*   Shift $(p_1, p_2, p_3)$ to the right by one. Now we have $p = (1, 2, 3, 4)$.\n\nHere, the total cost is $20 + 30 = 50$."},{"iden":"sample input 3","content":"1 10 10\n1"},{"iden":"sample output 3","content":"0"},{"iden":"sample input 4","content":"4 1000000000 1000000000\n4 3 2 1"},{"iden":"sample output 4","content":"3000000000"},{"iden":"sample input 5","content":"9 40 50\n5 3 4 7 6 1 2 9 8"},{"iden":"sample output 5","content":"220"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}