27021번 - Paranoid Cows 다국어

Farmer John's N cows (1 ≤ N ≤ 100,000) are self-conscious about their milk output. A cow who does not produce much milk is likely to be teased by the other cows.

FJ has designed a milking schedule for the cows in which every cow i (i is a cow index in the range 1..N) is assigned to an interval of time A[i]..B[i] (0 ≤ A[i] < B[i] ≤ 1,000,000,000). The cow must enter the barn at time A[i] for milking and depart from the barn at time B[i]. The door to the barn is narrow and can accommodate at most one cow at a time, so FJ has designed his schedule so that no two cows enter or leave at the same time.

Suppose the milking interval for some cow i contains the interval for some other cow j. That is, A[i] < A[j] < B[j] < B[i]. In this case, we say these two intervals "nest". Nesting intervals are bad, since in this case cow i is in the barn for the entire duration of cow j's milking and as a result, cow i can spy on cow j and determine her milk output. Since cows are paranoid about other cows knowing their milk output, FJ hopes his schedule does not contain any nested intervals.

Please help FJ by determining the largest index K (1 ≤ K ≤ N) such the intervals of cows 1..K have no occurrences of nesting.

• Line 1: The number of cows, N
• Lines 2..N+1: Two space-separated integers that are respectively the start and end times of a cow's milking interval

• Line 1: A single integer, k.