인형 timer 1s memory 1024MB

정올 유치원에서는 물체의 크다 작다 개념을 가르치고 있다. 정올 유치원의 스타 서현샘은 이 개념을 가르치기 위해 인형을 활용하기로 했다.

모든 인형은 안이 비어있는 구조로 되어 있어서 큰 인형 안에 작은 인형을 집어 넣을 수 있으며, 모든 인형은 각각 고유의 크기를 가지고 있다.

다음과 같은 조건을 만족하면 크기 x인 인형은 크기 y인 인형의 안에 넣을 수 있다.

y-x \ge 2

다시 말해, 크기 차이가 2 이상이면 작은 인형 위에 큰 인형을 포갤 수 있다는 것이다.

서현샘은 여러 인형들 중 몇 개를 선택한 후 가장 작은 인형을 두 번째로 작은 인형에 넣는 방식으로 하나의 인형으로 보이도록 하고 싶다.

이렇게 만든 "인형의 무게"은 그 인형을 만드는데 사용된 인형의 수로 정의한다.

n일 동안 서현샘은 인형을 구매하려고 한다. i일차에 (1 \le i \le n) 구매하는 인형의 크기는 a[i]이며 인형을 구매한 다음 위 방법으로 포개어 가장 무거운 "인형의 무게"를 구하려고 한다.

정올 유치원의 스타 서현샘을 도와 인형을 구매할 때마다 만들 수 있는 가장 무거운 "인형의 무게"를 구하라.

[제약 조건]

1 \le n \le 100,000

1 \le a[i] \le 500,000