만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

폭탄 해제

면접 대비

시간 제한2초메모리 제한1024 MB

요약
버튼 값들과 목표 합 k가 주어질 때, 활성 버튼 중 두 값의 합이 k가 되지 않도록 끌 버튼의 최소 개수를 구합니다.
난이도

보통10점 중 4점

유형
해시맵, 그리디
정답자
아직 제출이 없습니다

문제

나이트시티에서 Ви가 워트슨 지역 한가운데에 있는 폭탄을 해제하려고 목숨을 걸고 있다. 폭탄에는 정확히 nn개의 버튼이 있고, 각 버튼에는 자연수가 적혀 있다. 각 버튼은 활성 상태이거나 비활성 상태이며, 버튼을 누르면 상태가 바뀐다. 한 번 누르는 데 정확히 1초가 걸린다. 처음에는 모든 버튼이 활성 상태이다.

폭탄은 카운트다운이 끝난 시점에 활성 상태인 버튼 중 두 개의 수의 합이 정확히 kk가 되는 쌍이 있을 때에만 폭발한다. 폭탄이 터지지 않도록 하는 데 필요한 버튼 누름 횟수의 최솟값을 구하라.

입력

첫 줄에 정수 nn과 kk가 주어진다 (1≤n≤100 0001 \le n \le 100\,000, 1≤k≤1091 \le k \le 10^9). 둘째 줄에는 버튼에 적힌 정수 aia_i nn개가 주어진다 (1≤ai≤1091 \le a_i \le 10^9).

출력

폭탄을 해제하는 데 필요한 버튼 누름 횟수의 최솟값을 한 줄에 출력한다.

예제2

  1. 예제 1

    입력
    5 100
    77 23 45 54 22
    
    예상 출력
    1
    
  2. 예제 2

    입력
    7 7
    4 3 4 8 4 3 4
    
    예상 출력
    2