Trending Hashtags

A new social media company is planning to develop a feature to detect trending hashtags in user posts. A trending hashtag is defined as the hashtag that appears most frequently within a sliding window of a fixed size k. In the event of a tie, the hashtag with the smallest numerical value is chosen.

More formally, given a sequence of hashtags represented as integers and a sliding window of size \( k \), for each window you are to determine the hashtag with the maximum frequency. If more than one hashtag has the same maximum frequency, output the one with the smallest value.

The sliding window moves one position forward at a time. For example, if the input array is \( A = [a_1, a_2, \dots, a_n] \), then the first window comprises \( a_1 \) to \( a_k \), the second window comprises \( a_2 \) to \( a_{k+1} \), and so on until the window covers \( a_{n-k+1} \) to \( a_n \).

Your task is to implement this functionality. Use the formula for frequency as follows:

[ \text{frequency}(x) = #{i \mid a_i = x} ]

inputFormat

The input is read from standard input (stdin) and consists of three lines:

• The first line contains an integer \( n \), the number of hashtags.
• The second line contains \( n \) space-separated integers representing the hashtags.
• The third line contains an integer \( k \), the size of the sliding window.

outputFormat

Output the most frequent hashtag for each sliding window as a sequence of space-separated integers on a single line. If multiple hashtags are tied for maximum frequency within a window, output the smallest one.

10
3 3 1 2 2 2 1 3 3 3
3

3 1 2 2 2 1 3 3