CodeForces

Once Bob saw a string. It contained so many different letters, that the letters were marked by numbers, but at the same time each letter could be met in the string at most 10 times. Bob didn't like that string, because it contained repeats: a repeat of length x is such a substring of length 2x, that its first half coincides character by character with its second half. Bob started deleting all the repeats from the string. He does it as follows: while it's possible, Bob takes the shortest repeat, if it is not unique, he takes the leftmost one, and deletes its left half and everything that is to the left of this repeat.

You're given the string seen by Bob. Find out, what it will look like after Bob deletes all the repeats in the way described above.

Input

The first input line contains integer n (1 ≤ n ≤ 10⁵) — length of the string. The following line contains n space-separated integer numbers from 0 to 10⁹ inclusive — numbers that stand for the letters of the string. It's guaranteed that each letter can be met in the string at most 10 times.

Output

In the first line output the length of the string's part, left after Bob's deletions. In the second line output all the letters (separated by a space) of the string, left after Bob deleted all the repeats in the described way.

Example

Input

6
1 2 3 1 2 3

Output

3
1 2 3

Input

7
4 5 6 5 6 7 7

Output

1
7 

题意：给一个串，串中的每个数最多出现10次，从左到右进行扫描，如果遇到两个相同且相邻的子串，则删去左边的子串和它左边的部分。问扫描完成后剩下的串是什么？

分析：如果直接从前往后进行模拟，则复杂度较大。
题目中可以发现，每个数最多出现10次，所以直接记录每个数出现的位置，而因为范围是1-1e9，所以记录之前需要进行离散化处理
这样当我们在需要扫描在i位置前面且与从i开始的子串，相同且相邻的子串时，只需要考虑记录的那几个位置即可
而又因为每个数出现最多10次的关系。在扫描的时候没有很多相等的情况，大多数情况都会被排除，所以不会消耗太多的时间。

代码如下：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
typedef long long LL;
const int MAXN=1e5+100;
map<int,int>mp;
vector<int>V[MAXN];
int cnt,tel;
struct node
{
    int x;
    int id;
}a[MAXN];
int get_id(int x)
{
  if(mp.find(x)!=mp.end())return mp[x];
  return mp[x]=cnt++;
}
int main()
{
    ios::sync_with_stdio(false);
    int n,flag,tel;
    cin>>n;
    cnt=1;
    for(int i=1;i<=n;i++)
    {
      cin>>a[i].x;
      a[i].id=get_id(a[i].x);
    }
    for(int i=1;i<=n;i++)
    V[a[i].id].push_back(i);
    
    tel=0;
    for(int i=2;i<=n;i++)
    {
      for(int r=0;r<V[a[i].id].size();r++)
      {
          flag=0;
          int j=V[a[i].id][r];
          if(!(j>=1&&j<i&&(i-j)<=(n-i+1)))
          continue;
          if(j<tel)
          continue;
          flag=1;
          for(int k=0;k<i-j;k++)
          {
              if(a[j+k].x!=a[i+k].x)
              {
               flag=0;
             break;    
            }
        }
        if(flag==1)
        break;
      }
      if(flag==1)
          tel=i;
    }
    if(tel==0)
    {
     cout<<n<<endl;
     for(int i=1;i<=n;i++)
     i==1?cout<<a[i].x:cout<<" "<<a[i].x;
     cout<<endl;
     return 0;
    }
    cout<<n-tel+1<<endl;
    for(int i=tel;i<=n;i++)
    i==tel?cout<<a[i].x:cout<<" "<<a[i].x;
    cout<<endl;
    return 0;
}

CodeForces

相关推荐