Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

THEME - Đoạn cao trào của bản nhạc

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274566/problem/E

Trong một bản nhạc thường có những đoạn nhạc mà tác giả sử dụng nó nhiều lần ( ít nhất 2 lần ). Những đoạn đó gọi là "đoạn cao trào". Do có thể sử dụng nhiều giọng khác nhau ( son, la, si...) nên nốt đầu tiên của các lần xuất hiện có thể khác nhau, nhưng chệnh lệnh độ cao giữa hai nốt liên tiếp thì chắc chắn giống.
VD: hai đoạn sau
1 2 5 4 10

4 5 8 7 13
được coi là một đoạn cao trào, vì chúng cùng sự chênh lệch độ cao : +1,+3,-1,+6
Cho một bản nhạc, yêu cầu tìm độ dài đoạn cao trào dài nhất.
+ Đoạn cao trào phải có từ 5 nốt nhạc trở lên.
+ Những lần xuất hiện của đoạn không được chồng lên nhau ( không có nốt nhạc chung ).

Input

Dòng 1 : n = số nốt nhạc <= 5000
Một số dòng sau là n nốt nhạc, mỗi nốt được quy ra số tự nhiên trong phạm vi 1..88.

Output

1 dòng chứa 1 số duy nhất là độ dài đoạn cao trào dài nhất. Nếu không tìm được đoạn nhạc nào, in ra 0.

Example

Input:
30
25 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 18
82 78 74 70 66 67 64 60 65 80


Output:
5
(5 nốt cuối dòng 1 và 5 nốt đầu dòng hai cùng là một đoạn)

Được gửi lên bởi:Nguyen Minh Hieu
Ngày:2007-04-27
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:USACO , thanks Hoanh Tien

hide comments
2019-09-14 03:43:58
ban nhac ko cao trao
2018-12-13 15:20:35
SuffixArray
2017-08-19 11:14:20 Con Bò Huyền Thoại
https://kienthuc24h.com/theme-spoj-doan-cao-trao-cua-ban-nhac/
2016-08-18 10:25:30
QHD roi
2016-04-10 10:18:04
Hash O(n log n) AC
2015-11-12 16:15:39
THAM KHẢO TẠI https://traitaodo.wordpress.com/2015/11/12/doan-cao-trao-cua-ban-nhac-theme/
2015-10-30 15:35:54
Hash + binary search: n(log(n))^2

Last edit: 2015-10-30 15:36:13
2014-09-21 17:04:50 ∞Skyscraper∞
công nhận n^2 mà tle thật, chán
2014-07-23 06:29:59 Thcs Ðặng Chánh Kỷ
AC, duyệt thêm vòng tìm max là tle, ns chung là nên lược bớt những cái không cần thiết mới ac đc
2014-07-22 18:52:32 Thcs Ðặng Chánh Kỷ
Bài này ức chế quá, tối ưu đủ kiểu mà vẫn tle, hết tle lại wa

Last edit: 2014-07-23 06:28:35
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.