Let cost(l,r) count pairs of people in [l,r] who know each other. I need to verify QI: cost(a,c)+cost(b,d)≤cost(a,d)+cost(b,c) for a≤b≤c≤d. Consider any pair (x,y) with x<y. Count how many times it appears on each side:
1. Both in [b,c]: counted twice on both sides. Equal.
2. One in [a,b), one in [b,c]: left has 1 (via [a,c]), right has 2 (via both). Right wins.
3. One in [a,b), one in (c,d]: left has 0, right has 1 (via [a,d]). Right wins. Every pair contributes at least as much to the right side. QI holds.