Every day Kotlin heroes analyze the statistics of their website. For $n$ days, they wrote out $n$ numbers $a_1, a_2, \dots, a_n$, where $a_i$ is the number of visits on the $i$-th day.
They believe that a day is bad if there are at least $2$ days before it with a strictly greater number of visits. For example, if $n=8$ and $a=[3, 1, 4, 1, 5, 9, 2, 6]$, then the day $4$ is bad (because $a_4=1$, but there are $a_1=3$ and $a_3=4$). Also, the day with the number $7$ is bad too.
Write a program that finds the number of bad days.
Input
The first line contains an integer $n$ ($1 \le n \le 2\cdot10^5$), where $n$ is the number of days. The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the number of website visits on the $i$-th day.
Output
Print the number of bad days, i.e. such days that there are at least two days before it with a strictly greater number of visits.
Examples
input
8 3 1 4 1 5 9 2 6
output
2
input
5 1 1 1 1 1
output
0
input
13 2 7 1 8 2 8 1 8 2 8 4 5 9
output
6
Solution:
fun main(args: Array<String>) {
val n = readLine()!!.toInt()
val a = readLine()!!.split(" ").map { it.toInt() }
var m1 = 0
var m2 = 0
var ans = 0
for (c in a) {
if (c > m1) {
m2 = m1
m1 = c
} else {
if (c >= m2) {
m2 = c
} else {
ans++
}
}
}
println(ans)
}
