题目内容：

 

C. Lose it!

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array aa consisting of nn integers. Each aiai is one of the six following numbers: 4,8,15,16,23,424,8,15,16,23,42.

Your task is to remove the minimum number of elements to make this array good.

An array of length kk is called good if kk is divisible by 66 and it is possible to split it into k6k6 subsequences 4,8,15,16,23,424,8,15,16,23,42.

Examples of good arrays:

  • [4,8,15,16,23,42][4,8,15,16,23,42] (the whole array is a required sequence);
  • [4,8,4,15,16,8,23,15,16,42,23,42][4,8,4,15,16,8,23,15,16,42,23,42]
  • [][]

Examples of bad arrays:

  • [4,8,15,16,42,23][4,8,15,16,42,23] (the order of elements should be exactly 4,8,15,16,23,424,8,15,16,23,42);
  • [4,8,15,16,23,42,4][4,8,15,16,23,42,4] (the length of the array is not divisible by 66);
  • [4,8,15,16,23,42,4,8,15,16,23,23][4,8,15,16,23,42,4,8,15,16,23,23] (the first sequence can be formed from first six elements but the remaining array cannot form the required sequence).

Input

The first line of the input contains one integer nn (1≤n≤5⋅1051≤n≤5⋅105) — the number of elements in aa.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (each aiai is one of the following numbers: 4,8,15,16,23,424,8,15,16,23,42), where aiai is the ii-th element of aa.

Output

Print one integer — the minimum number of elements you have to remove to obtain a good array.

Examples

input

Copy

5
4 8 15 16 23

output

Copy

5

input

Copy

12
4 8 4 15 16 8 23 15 16 42 23 42

output

Copy

0

input

Copy

15
4 8 4 8 15 16 8 16 23 15 16 4 42 23 42

output

Copy

3

解题思路:

 刚开始以为用dp或者纯暴力,暴力会时间超限，后来想到可以直接用数组模拟，时间复杂度为O(n)

先用map记录4,8,15,16,23,42的下标分别为1,2,3,4,5,6，用 vis数组记录下标出现的次数  当遍历数组时，

遇到一个数的下标为2-5，则记录一下，也就是说把当前下标的前一个下标vis值减一，当前下标的vis值加一,

最后结果为n-6*good数组的个数

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
int n,m,vis[10];
map<int,int>mp;
void init()
{
    mp[4]=1;
    mp[8]=2;
    mp[15]=3;
    mp[16]=4;
    mp[23]=5;
    mp[42]=6;
    memset(vis,0,sizeof(vis));
}
int main()
{
    while(cin>>n)
    {
        init();
        for(int i=1; i<=n; i++)
        {
            cin>>m;
            if(mp[m]==1)
                vis[1]++;
            else if(vis[mp[m]-1]>0)
            {
                vis[mp[m]-1]--;
                vis[mp[m]]++;
            }
        }
        cout<<n-vis[6]*6<<endl;
    }
    return 0;
}