Generate a Monotonic Function

Pyth, 35 bytes (38 - 15% = 31.45 farther down)

#I!sm><FhMds<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><FhMds<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.