http://www.51nod.com/tutorial/course.html#!courseId=15
解题关键：主要是一种思想
$dp[i] = dp[i - 1]*2$ 如果a[i]不在之前出现
$dp[i] = dp[i - 1]*2 - dp[j - 1]$，如果a[i]最近在j的位置出现过。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+;
ll a[],have[],dp[];//have存的是位置
int main(){
int n;
cin>>n;
for(int i=;i<=n;i++){
cin>>a[i];
} //注意要从1开始读
dp[]=;
for(int i=;i<=n;i++){
dp[i]=dp[i-]*%mod;
if(have[a[i]]>) dp[i]=(dp[i]-dp[have[a[i]]-]+mod)%mod;
have[a[i]]=i;
}
printf("%lld\n",(dp[n]-+mod)%mod);
}