Recall from class how to prove non$-$membership in a sorted merkle tree $($representing a sorted array$).$ Instead consider the case where the array elements are not sorted, but broken into two lists, each of them sorted, and then joined. If you were to plot it$,$ it may look like any of the following. $($Note that we don't guarantee how the elements in the two sets are related. All we know is that each of the two arrays is sorted. Pictures illustrate combinations of ascending$/$descending sorted subarrays. They are for illustration only; don't rely on them as a definitive way to interpret the task$)$

${?}^1$ As $d$ grows, $2^{-d}$ becomes a smaller target to hit by fixing how many leading zeros of the hash function are required. If $d=1,$ then the target is $\frac{2^{}}{2},$ which means you have a $\frac{1}{2}$ chance of solving with a single calculated hash. When $d=2,$ you have a $\frac{1}{4}$ chance with a single hash, and so on$.$ In reality, this parameter changes with the world hashrate to keep the average blocktime constant.

HW$2-2$

How would you $($prover$)$ show non$-$membership in an array that looks like this? You may assume the two trees have equal number of leaves. Prover has read$-$only access to the resulting data structure. That is$,$ it can read it all, but can't manipulate$/$sort$/$rearrange etc. The verifier is given the Merkle root joining the two Merkle trees. Verifier knows that each of the two subtrees is sorted.

Argue why your solution is a valid proof system.