链接：
https://ac.nowcoder.com/acm/contest/33192/E
来源：牛客网
Recently, Grammy has learned ternary search in Tony's class. She can find the peak value in an array using this algorithm when the array is unimodal. Here we define an array
a1,a2,...,ana_1,a_2,...,a_na1,a2,...,an is unimodal if and only if it satisfies one of the following conditions:
-
There exists an index kkk (1≤k≤n1\leq k\leq n1≤k≤n) such that a1<a2<...<ak>ak+1>...>ana_1 < a_2 < ... < a_k > a_{k+1} > ... > a_na1<a2<...<ak>ak+1>...>an.
-
There exists an index kkk (1≤k≤n1\leq k\leq n1≤k≤n) such that a1>a2>...>ak<ak+1<...<ana_1 > a_2 > ... > a_k < a_{k+1} < ... < a_na1>a2>...>ak<ak+1<...<an.
As the tutor of Grammy, Tony wants to examine whether Grammy fully understands what he taught in class so he leaves
nnn tasks for Grammy to try ternary search. The tasks are as follows.
Initially, there is an empty array. Each task appends a
distinct number at the right end of the array and Grammy should do ternary search on it. However, due to Tony's carelessness, the array may not be unimodal after some addition. Since Tony has already slept, Grammy has to solve the problem by herself.
For each task, some operations should be taken before Grammy tries ternary search on it to make it unimodal. For each operation, Grammy can swap the values of
aia_iai and
ai+1a_{i+1}ai+1 for some
iii (
1≤i<n1\leq i < n1≤i<n). Grammy is a lazy girl and she thinks that if she has to do many operations, she would like to wait for Tony to wake up and solve the problem. For each task, she wonders how many operations she has to do at least to make the array unimodal. Can you help her?