만드는 중입니다

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

아즈버의 이빨 자국

면접 대비

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

요약
정렬된 이빨 자국 위치가 주어질 때, 모든 자국마다 정확히 k만큼 떨어진 다른 자국이 있는 간격 k를 모두 구합니다.
난이도

보통10점 중 5점

유형
배열, 해시맵, 완전 탐색
정답자
아직 제출이 없습니다

문제

집 안의 먹을 것이 계속 사라진다. 당신은 이웃집 곰 아즈버(azber)를 의심하고 있다. 오늘 드디어 결정적인 증거를 찾았는데, 바로 쵸코바에 찍힌 이빨 자국이다!

당신은 아즈버가 커다란 두 송곳니로 쵸코바를 물어 여러 번 자국을 남겼다고 생각한다.

쵸코바를 수직선이라고 하자. 아즈버는 다음 규칙에 따라 쵸코바에 이빨 자국을 남길 수 있다.

  • 처음에 쵸코바에는 자국이 없다.
  • 아즈버의 송곳니 사이 간격이 kk(k>0k > 0)일 때, 아즈버는 00 이상의 수 xx를 골라 쵸코바의 xx와 x+kx + k 위치에 자국을 남기는 행동을 00회 이상 반복할 수 있다.
  • 같은 위치에 여러 번 자국을 남기더라도 마지막에 남긴 자국만 보인다.

당신은 쵸코바에 남은 이빨 자국을 바탕으로 송곳니 사이 간격 kk가 될 수 있는 수를 모두 적어 두었다가, 나중에 아즈버를 만나면 확인하려고 한다.

이빨 자국의 위치가 주어질 때, 아즈버의 송곳니 사이 간격이 될 수 있는 수를 모두 구해 보자!

입력

첫째 줄에 쵸코바에 찍힌 이빨 자국의 개수 NN이 주어진다. (2≤N≤4 0002 \le N \le 4\,000)

둘째 줄에 이빨 자국의 위치 x1,x2,…,xNx_1, x_2, \ldots, x_N이 공백을 사이에 두고 오름차순으로 주어진다. 모든 xix_i는 서로 다르다. (0≤xi≤1090 \le x_i \le 10^9)

출력

첫째 줄에 아즈버의 송곳니 사이 간격이 될 수 있는 수의 개수 KK를 출력한다.

KK가 11 이상이면, 둘째 줄에 송곳니 사이 간격이 될 수 있는 수를 공백을 사이에 두고 오름차순으로 출력한다.

예제3

  1. 예제 1

    입력
    4
    0 5 10 15
    
    예상 출력
    2
    5 10
    
  2. 예제 2

    입력
    4
    0 1 3 5
    
    예상 출력
    0
    
  3. 예제 3

    입력
    2
    5 28
    
    예상 출력
    1
    23