Because of necessary software maintenance, Jutge.org may not fully work on the 7 of may, from 8 to 10 CEST.

Intervals dins d'intervals P40985

Statement

html

Donats diversos intervals [a_i, b_i], determineu quants d’ells estan continguts en algun altre.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb un nombre n entre 0 i 10⁴, seguit de n intervals de nombres enters [a_i, b_i]. Suposeu a_i < b_i, i que per a tot parell i ≠ j, a_i ≠ a_j, b_i ≠ b_j, i a_i ≠ b_j.

Sortida

Per a cada cas, escriviu el nombre d’intervals continguts en algun altre.

Pista

La solució esperada té cost Θ(n logn). Usar el procediment @sort()@ per ordenar amb algun criteri adequat us hauria de ser útil.

Public test cases

Input

3   0 1  2 3  4 5
3   0 5  1 4  2 3
0
1   -3 0
4   -30 30  20 40  -10 10  -40 -20

Output

Information

Author: Amalia Duch
Language: Catalan
Official solutions: C++
User solutions: C++