H - Discarding Triplets Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

あなたは N 枚のカードを手札に持っており、i \, (1 \leq i \leq N) 枚目のカードには整数 A_i が書かれています。あなたは次の操作を好きな回数行うことができます。

  • 書かれている整数が連続しているような 3 枚のカードを選び、それらを手札から捨てる。言い換えると、ある整数 x に対し、x, x+1, x+2 が書かれているカードを 1 枚ずつ選び、それらを手札から捨てる。

手札のカードを最小で何枚に減らすことができますか？

制約

  • 3 \leq N \leq 3 \times 10^5
  • 1 \leq A_i \leq 10^{18} \, (1 \leq i \leq N)
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 \ldots A_N

出力

答えを出力せよ。

入力例 1

7
2 4 2 1 6 3 5

出力例 1

1

次の 2 つの操作を行うことで、手札に残るカードは 1 枚になり、これが最小です。

  • 1, 2, 3 が書かれたカードを選び、これらを捨てる。
  • 4, 5, 6 が書かれたカードを選び、これらを捨てる。

入力例 2

10
1 2 2 4 6 7 9 9 10 12

出力例 2

10

入力例 3

3
999999998 999999999 1000000000

出力例 3

0

Problem Statement

You have a hand of N cards. The i-th card (1 \leq i \leq N) has an integer A_i written on it. You can perform the following operation any number of times.

  • Choose three cards with consecutive integers written on them, and discard them from hand. In other words, for some integer x, choose a card with x, a card with x+1, and a card with x+2 written on them, and discard them from hand.

What is the minimum possible number of cards in your final hand?

Constraints

  • 3 \leq N \leq 3 \times 10^5
  • 1 \leq A_i \leq 10^{18} \, (1 \leq i \leq N)
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

Print the answer.

Sample Input 1

7
2 4 2 1 6 3 5

Sample Output 1

1

After the following two operations, your hand will have one card, which is the minimum possible.

  • Choose cards with 1, 2, 3 written on them, and discard them.
  • Choose cards with 4, 5, 6 written on them, and discard them.

Sample Input 2

10
1 2 2 4 6 7 9 9 10 12

Sample Output 2

10

Sample Input 3

3
999999998 999999999 1000000000

Sample Output 3

0