Archery Championship
InterviewTime limit2sMemory limit512 MB
Given a sequence of scores, find the best possible place of a participant whose score ends in 5, has a champion before him, and is followed immediately by a lower score.
- Level
Medium5 of 10
- Topics
- Array, Implementation, Greedy, Prefix sum
- Solved
- No attempts yet
Problem
The winner of a school-level informatics olympiad found, among old papers at home, the results of a national archery championship in which his father had participated. Unfortunately, the sheet with the results had deteriorated badly over time, and the surnames of the participants could not be made out. Only the points each participant scored remained, listed in the order in which the participants shot.
After asking his father, the student learned that the number of points his father scored ends in 5, that one of the champions shot before him, and that his father's friend, who shot immediately after his father, scored fewer points. Now he is interested in the highest place his father could have taken in that championship.
We say a participant took k-th place if exactly (k – 1) participants scored strictly more points than he did. All participants who took first place are considered champions.
Write a program that, given the results of the championship, determines the highest place the father of the winner of the school-level informatics olympiad could have taken.
Input
The first line of the input file contains an integer n, the number of participants in the national archery championship (3 ≤ n ≤ 105).
The second line of the input file contains n positive integers, each not exceeding 1000: the participants' points, given in the order in which they shot.
Output
The output file must contain a single integer: the highest place the student's father could have taken. If no participant of the championship satisfies the conditions described above, output 0.