Array Shuffling

Question

Write a program that takes a sorted integer array, shuffles all the elements in such a way that for every i there must exist a j such that, one of the following is satisfied:

a[i] < a[j] < a[i+1] 
a[i] > a[j] > a[i+1]

i and j are within the bounds of array.

If there are not many distinct elements, you must show an error.

For example,

Input: 1, 2
Output: Error

Input: 1, 2, 3, 4, 5, 6, 7
Output: 7, 1, 4, 2, 5, 3, 6

Input: 1, 2, 2, 4, 5, 6, 7
Output: 1, 4, 6, 2, 5, 2, 7 

Input: 1, 2, 2, 3
Output: Error

Input: 1, 5, 7, 7, 11
Output: Error

There may be more than one possible correctly shuffled arrays. You just have to solve for 1 correct solution.

Input array can have repeated elements, this requirement makes the solution tricky, otherwise a sort and skip would have worked.

Being able to have duplicates in input also makes it different from The Strange Unsorting Machine for Nefarious Purposes . And a correct solution is much trickier than the that.

The output must be of same size as input array and all elements from the input array must exist at some position in the output array.

How to take input: The program must take input either through console input or a simple delimited text file.

How to output: The program must output to the console.

What to output: Program must output both the input and the output array in following format

Input: 1, 2, 3, 4, 5, 6, 7
Output: 7, 1, 4, 2, 5, 3, 6 

If input cannot be shuffled as required, the output should look like

Input: 1, 2, 3
Output: Error

Shortest code (byte count) wins.

BONUS 1: Deduct 10 points from your count if your solution can work on unsorted inputs.

BONUS 2: Deduct 20 points from your count if your solution can find more than 1 (not all) solutions for the same input. To qualify for this bonus, your additional solution must not be just a reversed output of the other solution.

Answer 1

Haskell, 311276 (-30 bonus=246)

import Data.List
m=map
w=putStrLn
b=(intercalate",").(m show)
o="Output: "
z[]=[o++"Error"]
z a=m((o++).b)a
main=do
 r<-getLine
 let q=m read(words r)::[Int]
 w$"Input: "++b q
 mapM_ w$z$filter(\d->and$m(\(a,b)->any(\x->(a<x&&x<b)||(a>x&&x>b))d)$zip d(tail d))$permutations q

Compile with ghc, Run from the command line, input is a single line with space delimited numbers, eg echo 1 2 3 4|shuffle. This is a brute force solution so is quite likely to be slow for large input lists. It prints all the solutions.