Codeforces 321E Ciel and Gondola - Why QI Holds

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) \leq cost(a,d) + cost(b,c)$ for $a \leq b \leq c \leq 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.