TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

71.4% (5/7)

Tags

Description

某一天 oaix_cire 在建中遇到了一台玻璃琴,因為玻璃琴使出了擋路:

於是 oaix_cire 就把玻璃琴移走了,這就是成語「移建中琴」的典故。

剛拿到全國音樂能力競賽一等一的 KCZ 覺得這樣太可惜了,於是就用玻璃琴演奏了一段自創的樂曲給國手 xbq2 聽。由於 xbq2 是虛擬歌手愛好者,因此他也用很數位的方式來剖析這首歌。xbq2 將樂曲中每個音符的頻率依序用一個數字紀錄 a1,a2,,aN(由於是虛擬的,因此 ai 有可能是負的),如果連續的兩個音頻率差距太大,這首歌聽起來就會不太和諧,具體來說,一首歌的不和諧度 f(a)a 所有相鄰項差的積,也就是:f(a)=i=2Naiai1

身為預測大師,ptnilyoj 想要在 xbq2 吃完拉麵前就知道他會給出什麼評價。雖然 xbq2 沒有明確指出不和諧度和評價之間是怎麼換算的,但根據 ptnilyoj 的經驗法則,xbq2 給出的評價 g(x) 和不和諧度 x 的關係滿足以下式子:g(x)=2x2+1另外,由於小數點是一件麻煩的事情,因此 xbq2 只會回報 g(x) 的整數部分(也就是如果原始評價是 k,xbq2 會說這首歌的評價是 k)。

請幫幫 ptnilyoj,說不定他會因此不再預(ㄕㄨ)測(ㄈㄨˊ)你 (?)

Input Format

第一行有一個正整數 N,代表 KCZ 創作的這首歌一共有 N 個音符。
第二行包括 N 個整數 ai,依序代表第 i 個音符的頻率。

  • 2N106
  • |ai|109

Output Format

輸出一個整數 K,代表 xbq2 對這首歌的評價的整數部分(取下高斯後的結果)。

Sample Input 1

2
1 1

Sample Output 1

2

Hints

Problem Source

IOICamp 2021 Day2 pC

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~29 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 262144 65536 1 2
1 2000 262144 65536 2
2 2000 262144 65536 2
3 2000 262144 65536 2
4 2000 262144 65536 2
5 2000 262144 65536 2
6 2000 262144 65536 2
7 2000 262144 65536 2
8 2000 262144 65536 2
9 2000 262144 65536 2
10 2000 262144 65536 2
11 2000 262144 65536 2
12 2000 262144 65536 2
13 2000 262144 65536 2
14 2000 262144 65536 2
15 2000 262144 65536 2
16 2000 262144 65536 2
17 2000 262144 65536 2
18 2000 262144 65536 2
19 2000 262144 65536 2
20 2000 262144 65536 2
21 2000 262144 65536 2
22 2000 262144 65536 2
23 2000 262144 65536 2
24 2000 262144 65536 2
25 2000 262144 65536 2
26 2000 262144 65536 2
27 2000 262144 65536 2
28 2000 262144 65536 2
29 2000 262144 65536 2