题目大意：

首先，给你一个数列1e6，并给定你一个数字A，然后让你选出一个数字B，满足，对于数列中任意一个位置，该位置之前出现的A的个数不大于B出现的次数。

分析:

首先，我用一个跳跃数组a[i]来表示值i是否可能是答案。这里我说的跳跃数组就是，对于数组的某一个位置，我可以直接跳到它的下一个位置或者上一个位置，这样我就可以在删除其中的若干元素之后在下一次遍历的时候，不遍历这些被删除的元素。然后我就按照所给数列出现的顺序一个一个的添加到计数数组num中去，遇到数字A，我就遍历一遍跳跃数组并删除所需删除的元素。

下面分析一下这个办法的时间复杂度：

首先，出现一个数字A，就会遍历一次跳跃数组，那么，A第i次出现的时候，跳跃数组需要遍历的位置最多只需要n/i次。那么总的遍历次数就是 n×(1+12 +13 +14 +。。+1m )  ，m为A出现的次数，那么这个值最大就是 n×(1+12 +13 +。。。+1n )  。当n取1e6的时候，我用代码算了一下，是1.43927×1e7，这个复杂度应该是可以过的。

后续：

然后看了下别人的代码，好像我就是想麻烦了。只要用p和sum分别记录当前可以选择的最大值和最大值出现的次数，然后随着输入新的数，不断地更新这个信息就好了。同时记录每个数出现的次数。这样当一个数添加的时候，如果他之前出现的次数小于之前A出现的次数，那么我就不记录他的这次出现了，那么他就相当于永远不能超过A出现的次数了。这样一次遍历O(n)的时间就完成了解答。

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000500
#define maxe 1000000
struct node
{
    bool can;//是否可能为答案
    int next;//下一个可能为答案的位置标号
    int last;//上一个可能为答案的位置标号
}a[maxn];
int n,A,temp,first,appear_num[maxn],A_num;

void init()
{
    first=1;A_num=0;
    for(int i=0;i<maxn;i++)
    {
        a[i].can=1;
        a[i].next=i+1;
        a[i].last=i-1;
    }
}
void del(int x)
{
    a[x].can=0;
    if(a[x].last!=-1)a[a[x].last].next=a[x].next;
    if(a[x].next<=maxe)a[a[x].next].last=a[x].last;
    if(x==first)
    {
        first=a[x].next;
    }
}
int main()
{
    scanf("%d%d",&n,&A);
    init();
    del(A);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&temp);
        if(temp!=A)
        {
            if(a[temp].can==0)continue;
            appear_num[temp]++;
        }
        else
        {
            if(first>maxe)continue;
            int t=first;
            A_num++;
            while(t<=maxe)
            {
                if(appear_num[t]<A_num)
                {
                    del(t);
                }
                t=a[t].next;
            }
        }
    }
    //cout<<first;
    printf("%d",(first>maxe)?-1:first);
}