目錄

題目

輸入格式

輸出格式

樣例

提示

思路

代碼

---

題目

單點時限:?2.0 sec

內存限制:?512 MB

出題人當然是希望出的題目有關 oxx，于是想方設法給題目配上一些有關 oxx 的背景故事，使得它看起來不那么無趣。但有的時候卻無法引入合適的小姐姐，使得 oxx 顯得非?？蓱z。所以出題人刪除了故事，只留下一個枯燥乏味的數學問題。

【故事已刪除】

給一個長度為?n?的序列?a1,a2,…,an，求一個長度為?m?的序列?b1,b2,…,bm?使得：

• a1,a2,…,an?是?b1,b2,…,bm?的子序列（不一定連續(xù)），且
• 存在常數?p>0?使得?b1,b2,…,bm?是一個?p-莫干山序列。

序列?s1,s2,…,sn?是?p-莫干山序列，當且僅當：存在?0≤x<p?對于?1≤i≤n?滿足?si=(x+i)modp。

求?m?的最小值。

輸入格式

第一行一個整數?n?(1≤n≤2?105)。

第二行?n?個整數用空格隔開?a1,a2,…,an?(0≤ai≤109)。

輸出格式

輸出最小的?m。

樣例

input

2
0 2

output

3

input

3
0 2 0

output

4

input

1
0

output

1

input

10
0 1 2 3 5 6 7 8 9 1000000000

output

1000000001

input

3
0 1 2

output

3

提示

樣例 1: [0, 1, 2].

樣例 2: [0, 1, 2, 0].

樣例 3: [0].

思路

難度評級：??

重點是理解兩個概念：

1. 子序列雖然要求不一定連續(xù)，但是序列的元素順序不可以改變

2. 莫干山數列中的x要求是一個數，所有的si計算式子中的x都是同一個

代碼

#include <iostream>
#include <vector>
#include <cmath>using namespace std;
typedef long long ll;int main(int argc, char** argv) {int n;cin>>n;vector<int> vec(n);int maxN=-1;for(int i=0;i<n;i++) {cin>>vec[i];maxN=max(maxN,vec[i]);}ll ans=1;for(int i=1;i<n;i++) {if(vec[i]>vec[i-1]) ans+=vec[i]-vec[i-1];else ans+=maxN-vec[i-1]+vec[i]+1;}cout<<ans;return 0;
}