Codeforces Round #565 (Div. 3) C. Lose it!

Codeforces Round #565 (Div. 3)

 

C. Lose it!

You are given an array a consisting of n integers. Each ai is one of the six following numbers:  4,8,15,16,23,42.

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

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

Examples of good arrays:

  • [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] (the first sequence is formed from first, second, fourth, fifth, seventh and tenth elements and the second one is formed from remaining elements);
  • [][] (the empty array is good).

Examples of bad arrays:

  • [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] (the length of the array is not divisible by 66);
  • [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 n (1≤n≤5⋅105) — the number of elements in a.

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

Output

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

Examples

input

5

4 8 15 16 23

output

5

input

12

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

output

0

input

15

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

output

3

 

题意:

 

思路:

 

(题意思路有空再补,orzorz)

 

 

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<queue>
10 using namespace std;
11 #define ll long long 
12 const int mod=1e9+7;
13 const int inf=1e9+7;
14 
15 //const int maxn=;
16 
17 queue<int>q[6];
18 
19 ll int cnt=0;
20 
21 void solve()
22 {
23     while(!q[0].empty())
24     {
25         int now=q[0].front();
26         for(int i=1;i<6;i++)
27         {
28             if(q[i].empty())
29             {
30                 return ;
31             }
32             if(q[i].front()>now)
33             {
34                 now=q[i].front();
35                 continue;
36             }
37             else if(q[i].front()<now)
38             {
39                 q[i].pop();
40                 while(q[i].front()<now)
41                 {
42                     if(q[i].empty())
43                     {
44                         return ;
45                     }
46                     q[i].pop();
47                 }
48                 now=q[i].front();
49             }
50         }
51         cnt++;
52         for(int i=0;i<6;i++)
53             q[i].pop();
54     }
55 }
56 int main()
57 {
58     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
59     int n;
60     cin>>n;
61     int num;
62     for(int i=0;i<n;i++)
63     {
64         cin>>num;
65         if(num==4)
66             q[0].push(i);
67         else if(num==8)
68             q[1].push(i);
69         else if(num==15)
70             q[2].push(i);
71         else if(num==16)
72             q[3].push(i);
73         else if(num==23)
74             q[4].push(i);
75         else if(num==42)
76             q[5].push(i);    
77     }
78     
79     cnt=0;
80     
81     solve();
82     
83     cout<<n-6*cnt<<endl;
84     
85     return 0;
86 }

 

上一篇:洛谷 P1802 (选与不选都有价值)


下一篇:Codeforces Round #565 (Div. 3) C. Lose it!