TopCoder

WeaK
weak.infor.org 雖然這裡好像沒什麼東西。

User's AC Ratio

100.0% (10/10)

Submission's AC Ratio

58.6% (17/29)

Tags

Description

給一串數字h1,h2,h3,...,hn,這串數字的爛度定義成:

H = |h1-h2|+|h2-h3|+...+|hn-1-hn|

現在你要修改這串數字,使得爛度儘量小。

對於每個數字,你可以讓它和其它的任何數字交換,只能換一次,也可以不換。

找出每個數字分別該和哪個數字交換,才可以讓爛度最小。

Input Format

輸入的第一行有一個整數T,代表接下來有幾組測資。

每組測資的第一行有一個數N(N<1000),代表這組測資有幾個數字,

第二行有N個正整數為h1,h2,h3,...,hN,每個數字皆不超過10000

Output Format

對於第i個數字,如果它和第j個數字交換可以使爛度最小則輸出j,如果有多個j可以讓爛度最小,輸出最小的j。

格式詳見範例。

Sample Input

2
5
2 3 4 5 7
5
7 2 3 1 5

Sample Output

1 2 3 4 5
4 5 2 1 2

Hints

Problem Source

原TIOJ1329 / TFcis10 留社考。Problem Setter:seanwu

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 262144