Lanran opened a pet adoption center. Each pet has a characteristic value \((0<p<2^{31})\) and each adopter also has a value \(q\) \((0<q<2^{31})\).
Lanran needs to provide the following services:
- For a pet with characteristic value \(p\) arriving, it will be adopted by a person staying in the center whose \(q\) is the minimum closest to \(p\) or stay in the center if there is no adopter left.
- For an adopter with value \(q\) arriving, he/she will choose a pet staying in the center whose \(p\) is the minimum closest to \(q\) or stay in the center if there is no pet left.
\(a\) is the minimum closest to \(v\) in set \(S\) if and only if:
- for all \(a_x\in S\) there is \(|a-v|\le |a_x-v|\)
- for all \(a_i\in S\) and \(|a-v|=|a_i-v|\) there is \(a\le a_i\)
the dissatisfaction for each adoption is defined as \(|p-q|\)