개미 집합의 지름
Press the right button to connect the device.
Quiz Info
개미 집합의 지름
Easy
Category
Programming
Points
100p
Participant
570
Solved Rate
68%
15
35

문제


수직선 위에 개미 마리가 있다. 개미 집합의 지름이란, 개미 집합에 들어있는 임의의 두 개미 사이의 거리 중 가장 긴 거리를 뜻한다. 예를 들어, 개미 네 마리의 위치가 [1, 3, 2, 1] 이라고 하면 이 네 마리가 이루는 개미 집합의 지름은 2가 된다.

구름이는 주어지는 개미 집합의 지름을  이하로 만들어야 한다. 그러기 위해서는 개미의 일부를 제거해야 하는데, 구름이는 제거되는 개미가 불쌍하다고 생각하여 제거되는 개미의 수를 최소로 만들 것이다. 이때, 구름이가 제거해야하는 개미의 최소 수를 구하여라.


입력


첫째 줄에 가 공백을 두고 주어진다.
둘째 줄에 각 개미의 좌표  공백을 두고 주어진다.

  • 입력으로 주어지는 모든 수는 정수이다.


출력


구름이가 개미 집합의 지름을  이하로 만들기 위해 제거해야하는 개미의 최소 수를 출력한다.

Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
31
214
Output
1
Example 2
Input
30
777
Output
0
Example 3
Input
63
1346910
Output
3
Example 4
Input
115
1011121314151617181920
Output
5
⋇ Please keep the input and output formats carefully
Q&A
누구나 질문하고 답변할 수 있는 Q&A입니다. 문제를 풀며 어려웠던 부분에 대해 질문해보세요.
Registered Questions (0)