#CW9. 骰子塔(dice)

骰子塔(dice)

题目描述

有 NN 个正六面体骰子。每个骰子的六个面上各写有一个 11 到 66 之间的整数。同一个骰子任意两个不同的面上所写的数都不同,且任意两个相对的面上所写的数之和恒为 77。

现在每个骰子都被扔到地上,给出每个骰子的顶面上写的整数,第 ii 个骰子顶面的数是 aia_i。

要把骰子从下到上搭建成若干个骰子塔,有要求:

  • 每次从地面上拿起若干个骰子,搭建一个骰子塔,但不能改变骰子的朝向。
  • 所选骰子的排列顺序可以任意确定。
  • 任何两个相接触的面上所写的数必须相同。
  • 所有骰子都必须在某个骰子塔中使用。

请你合理决定搭塔方式,使最终建成的塔数最少。给定掷出 NN 个骰子后骰子顶面所写的数,请求出最终塔数的最小值。

输入格式

第一行给出整数 NN。

第二行依次给出 NN 个以空格分隔的整数 a1,a2,…,aNa_1, a_2, \ldots, a_N。

输出格式

第一行输出合理决定搭塔方式后,最终能够建成的塔数的最小值。

样例 1 输入

4
3 3 5 4

样例 1 输出

2

样例 2 输入

5
1 1 6 1 1

样例 2 输出

3

数据范围

对于所有测试数据,保证:2≤N≤2000002 \le N \le 200000,1≤ai≤61 \le a_i \le 6。

测试点 N≤N \le 特殊性质
1∼41 \sim 4 55 无
5∼75 \sim 7 3030
8∼108 \sim 10 10001000
11∼1411 \sim 14 200000200000 ai≤3a_i \le 3
15∼2015 \sim 20 无