I want to find an O(n) algorithm for this question, and we also need to prove the correctness (by induction) and the time complexity after coming up with an algorithm

Question 4. (30 points) Let S=x1x2xn be a sequence of numbers (possibly large and noninteger), and let p be an integer that is n. Give an O(n) time algorithm that, when given S and p as input, computes s1,s2,,snp+1 where si=max{xi,xi+1,,xi+p1}. You cannot assume that p is constant. We will give 20 points for a solution that runs in O(nlogp) time; for the full 30 points the solution must run in O(n) time. No points are given for the brute-force solution that takes O(p(np)) time