1085. How Many Are Beaten on Both Counts

n characters are given, each with an ATTACK and a DEFENCE. A character is WEAK when some other character has strictly greater attack AND strictly greater defence.

Print how many characters are weak.

(5,5) (6,3) (3,6) -> 0 (2,2) (3,3) (1,1) -> 2 (1,5) (10,4) (4,3) (4,3) -> 2 (7,7) (1,2) (2,1) (6,6) (8,8) -> 4

In the third row, (4,3) appears twice and both copies are beaten by (10,4). The pair (1,5) is beaten by nobody, since (10,4) has less defence.

## What most people try first

Compare every pair: O(n^2), which is 10^10 at n = 100000. It is the brute force this problem was checked against.

## Sort by attack descending, then sweep with a running maximum defence

sort by attack DESCENDING; among equal attacks, by defence ASCENDING best = -infinity count = 0 for each (a, d) in that order: if d < best: count += 1 else: best = d

## Why the tie-break is the whole problem

Sorting by attack descending means everyone already seen has attack at least as large as the current character. best is the largest defence among them. If d < best, somebody seen earlier has both a larger-or-equal attack and a strictly larger defence, and we need STRICTLY larger attack.

That is where the tie-break earns its keep. Among characters with the SAME attack, sorting by defence ascending means that when a character is examined, every earlier character with the same attack has a defence at most this one's, so none of them can have contributed a best above d. Only strictly larger attacks can have.

Sorting equal attacks by defence DESCENDING instead reports (1,1) as weak against (1,2), which is wrong because their attacks are equal. The test with three characters all of attack 1 is exactly that case.

## Why one number is enough

The condition "somebody with strictly greater attack also has strictly greater defence" only needs the MAXIMUM defence among those with strictly greater attack, because any defence below the maximum is irrelevant to a "is there one" question. So a single running maximum replaces the whole set.

## The elif, not a second if

best must be updated only when d >= best, which the else branch does for free. Updating it unconditionally with best = max(best, d) gives the same value and is also correct here; what is NOT correct is testing d < best after the update, which makes a character beat itself.

## Overflow

Attack and defence reach 10^9, inside the signed 32 bit limit of 2147483647, and nothing is added. The sentinel for "no defence seen yet" must be strictly below every possible defence; since defences are at least 1, both 0 and -1 work and 1 does not.

## Cost

Time O(n log n). Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ attack ≤ 1000000000` - `1 ≤ defence ≤ 1000000000`