[Coci2012]ograda

时间限制:2s      空间限制:32MB

题目描述

有n个高度互不相同的木板。你需要用它们顺次连接拼成一段篱笆。并且每两
个相邻位置的木板的高度的大小关系已知。一段篱笆的美观度定义为每两个相邻
位置的木板的高度差的绝对值之和。 求一种木板放置顺序使得在满足给
定的大小关系的基础上使得美观度尽量大。 
 
 


输入格式


输出格式


样例输入

4 
5 7 4 9 
1 2 3 4 
 

样例输出

 
7 
2 4 1 3 

提示

 
First sample description: Mirko bought boards of heights 1, 2, 3 and 4. Fences similar to Slavko’s
that he can build are:
{1,3,2,4} - niceness 2+1+2=5
   {1,4,2,3} - niceness 3+2+1=6
   {2,3,1,4} - niceness 1+2+3=6
    {2,4,1,3} - niceness 2+3+2=7
   {3,4,1,2} - niceness 1+3+1=5

n <= 300,000. 


题目来源

没有写明来源