Server Time:

User's AC Ratio in this contest

69.0% (20/29)

Submission's AC Ratio in this contest

18.2% (20/110)

Description

偉杰作為銀行的新人會計師,要被迫接手一堆爛攤子
某個工作是這樣的,有個陳年老舊的紙本帳務要做整理
上面有 $n$ 個隨著時間 $i$ 變動的非負數數字 $a_i$,但其中有一些資料怎樣也找不到

偉杰想知道假如這些資料找到後,最大的漲跌變化最小是多少?
但明早會議就得做出一些進度報告了,來不及做一些很好的假設
偉杰只好假定未知數字統一為 $k$ (且精度為 $1$),要使得最大漲跌變化值 $m$ 最小化
這裡 $m$ 就是所有相鄰數字的絕對差值中的最大值,即 $m = \max\limits_{1\le i < n}{|a_i-a_{i+1}|}$

舉例來說,長度 $n = 6$ 的資料為 $a = (?, ?, 9, ?, 3, ?)$,其中 $?$ 代表未知數字
其中一種解 $k = 6$,則資料改為 $a = (6, 6, 9, 6, 3, 6)$,$m = 3$
若是 $k = 1.1$,則資料改為 $a = (1.1, 1.1, 9, 1.1, 3, 1.1)$,$m = 7.9$,這樣就不是偉杰要求的變化值

Input Format

第一列有個正整數 $n$ 代表資料長度 ($2 \le n \le 5\cdot 10^5$)
第二列有 $n$ 個數字 $a_i$ 表示資料上的數字,其中 $-1$ 為未知數字 ($-1 \le a_i \le 10^9$)

根據題意,資料上已知的數字皆非負數,不會有在 $(-1, 0)$ 中的數字

Output Format

輸出數字 $m$ 表示最大變化值

浮點數 $m$ 的精度最多只要求小數點後 $1$ 位

Sample Input 1

6
-1 -1 9 -1 3 3

Sample Output 1

3

Sample Input 2

5
1.2 -1 3 4.6 -1

Sample Output 2

1.7

Sample Input 3

2
-1 -1

Sample Output 3

0

Hints

第 2 筆範測的 $k$ 為 $2.9$

Problem Source

CODEFORCES 1301B Motarack's Birthday

Subtasks

No. Testdata Range Score
1 0~19 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1500 65536 65536 1
1 1500 65536 65536 1
2 1500 65536 65536 1
3 1500 65536 65536 1
4 1500 65536 65536 1
5 1500 65536 65536 1
6 1500 65536 65536 1
7 1500 65536 65536 1
8 1500 65536 65536 1
9 1500 65536 65536 1
10 1500 65536 65536 1
11 1500 65536 65536 1
12 1500 65536 65536 1
13 1500 65536 65536 1
14 1500 65536 65536 1
15 1500 65536 65536 1
16 1500 65536 65536 1
17 1500 65536 65536 1
18 1500 65536 65536 1
19 1500 65536 65536 1