Generate a Monotonic Function
Pyth, 35 bytes (38 - 15% = 31.45 farther down)

#I!sm&gt;&lt;FhMds&lt;MCeMd^JC,mOQK^UQvzK2JB


Demonstration

Input is in the format:

n
s


Output is in the format:

[[value, tuple], [value, tuple], ...]


Simply generates random possibilities and tests them.



Alternative 37 byte version which I believe qualifies for the bonus:

Of!sm&gt;&lt;FhMds&lt;MCeMd^T2mC,d^UQvz^UQ^Qvz


Demonstration

This starts by generating all possible monotonic functions, then outputs one at random. It is much slower, and tops out at 2,2.