암소라인업

농부 존은 소유하고 있는 소들의 사진을 찍기 위해 전문 사진 작가를 고용했다. 다양한 품종의 소를 소유하고 있는 존은 한 장의 사진에 모든 종의 소가 포함 되길 원한다.

N마리의 소가 모두 라인에 맞춰(즉, Y 좌표는 고정) 다양한 위치(즉, X 좌표로 값은 정수 값임)에 서 있다. 그리고 소들은 정수 값의 품종 아이디를 목에 걸고 있다. 존은 연속된 범위의 사진을 찍을 계획이다. 사진 비용은 크기에 비례한다. 즉, X 좌표의 범위가 작을수록 비용은 저렴해진다.

당신이 할 일은 존이 한 장의 사진에 모든 품종의 소들이 적어도 한 마리씩은 포함될 수 있게 하는 최소 비용을 계산하는 것이다.

입력

첫 번째 줄에 소들의 수 N이 입력된다. (1≤N≤50,000)

두 번째 줄부터 N개 줄에 걸쳐 소의 위치 (X 좌표)와 소의 품종 아이디(ID)가 공백으로 구분되어 입력된다. (1≤X, ID≤1,000,000,000)

출력

모든 품종이 포함되는 X 좌표의 최소 범위를 출력하라.

입력 예시

6
25 7
26 1
15 1
22 3
20 1
30 1

#include <cstdio>
#include <map>
#include <algorithm>

#define MAXN 50000

using namespace std;

map<int,int> C;
pair<int,int> cows[MAXN];

int N,K;

int photo(){
 int i,j,k;
 int min_cost = cows[N-1].first-cows[0].first;

 i = 0, j = -1, k = 0;

 while(i < N && j < N){
  while(k < K && ++j < N) k += !(C[cows[j].second]++);

  while(k >= K){
   min_cost = min(min_cost,cows[j].first-cows[i].first);
   k -= !(--C[cows[i++].second]);
  }
 }

 return min_cost;
}

int main(){

 int i;

 scanf("%d",&N);

 for(i = 0; i < N; i++){
  scanf("%d%d",&cows[i].first,&cows[i].second);
  C[cows[i].second] = 0;
 }

 K = C.size();
 sort(cows,cows+N);

 printf("%d\n",photo());
}