共3题，一个小时，按测试点给分，总分将作为复试结果的综合评价参考（不计入复试总分）

1.骑车路线

• 单点时限: 2.0sec内存限制:512 MB

Tomislav最近发现自己的身材完全走样了，她走楼梯都变得很累。一天早上她起来以后，她决定恢复姣好的身材。她最喜欢的运动是骑自行车，因此她决定在本地的小山上做一次旅行。
她骑自行车的路线可以描述为N个数字的数列，每个数字表示每一段路地海拔高度。Tomislav最感兴趣的是最长的高度一直上升的子序列，她称这一段路为爬坡， Tomislav只想考虑这段爬坡的高度差(即开始和最后的数字的差距)，而不是什么路程长度。
一段爬坡路被定义为至少两个连续的上升数列。例如，我们考虑如下路线数列12 3 5 7 10 6 1 11,这里有两个爬坡，第一个爬坡(3 5 7 10)的高度差是7，第二个爬坡的高度差是10 (1 11)。
帮助Tomislav计算高度差最大的爬坡的高度差。

输入格式

第一行是一个正整数 \( N (1 \leq N \leq 1000) \)描述了路线数列。
第二行有\( N \)个正整数，每个正整数\( P_i (1 \leq P_i \leq 1000) \)表示相应路段的海拔高度。

输出格式

所有爬坡中的最大高度差，如果路线数列里面没有爬坡，就输出0。

样例1

input

5
1 2 1 4 6

output

5

样例2

input

6
10 8 8 6 4 3

output

0

提示

• \(40\%\)数据保证 \( N \leq 50 \)
• 对于 \( 100\% \)数据保证 \( N \leq 1000 \)

2.最长美丽子串

• 单点时限: 1.0sec内存限制:512 MB

给定长度为n的字符串S,定义其子字符串为S中连续的字符所组成的字符串。
若个字符串的每一个字符都独一 无二，那么我们称这样的字符串是美丽的，例如abc是美丽的，但是abb不是美丽的。请输出S的最长美丽子串的长度。

输入格式

一行一个字符串S

输出格式

一行一个整数，表示答案。

样例1

input

abcddbcd

output

4

样例2

input

aaaa

output

1

样例3

input

aabbcc

output

2

提示

样例一中最长美丽字串为abcd，长度为4
样例二中最长美丽字串为a，长度为1
样例一中最长美丽字串为ab和bc，长度为2

数据规定

• \(30\% \) ：S长度 \( [1,100] \)
• \(60\% \) ：S长度 \( [1,10000] \)
• \(100\% \) ：S长度 \( [1,100000] \)

3.中位数

• 单点时限: 1.0 sec内存限制: 512 MB

给定\( n \)个数 \( A_1, A_2 , \cdots , A_n \) (保证\( n\)为奇数)和\(s\)，你可以任意修改其中的某些数，但每次修改会有代价，代价定义为:若将\(x\)修改为\(y\),则此次代价为\(|x – y| \)。
求最少花费多少代价使得修改后所有数的中位数为\(s\)。
\(A_1, A_2, \cdots , A_n\)的中位数定义为:将A_i从小到大排序后的第\( \frac{n}{2} \)+ 1项(\( n\)为奇数)。

输入格式

第一行两个整数 \(n,s \)。
第二行\(n\)个整数，表示 \( A_1, A_2, \cdots , A_n \)

输出格式

输出一个整数，表示使序列的中位数变为s的最小代价。

样例

input

5 3
0 0 0 3 5

output

3

提示

• 对于\( 20\% \) 数据：\( n \leq 20\)
• 对于 \( 40\% \) 数据：\( n \leq 1000\)
• 另外对于\( 30\% \) 数据：满足对于任意 \( i \in [1,n] , A_i=0 \)
• 对于所有数据，满足 \( 1 \leq n \leq 10^5 \)且n为奇数，\( 0 \leq s，A_i \leq 10^8 \)，且n个数中有超过 \( \frac{n}{2} \)个元素为0