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 is unimodal if and only if it satisfies one of the following conditions:

• There exists an index () such that .
• There exists an index () such that .

As the tutor of Grammy, Tony wants to examine whether Grammy fully understands what he taught in class so he leaves 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 and for some (). 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?

The input contains only a single case.

The first line contains a single integer  (), denoting the number of tasks. The -th line of the following  lines contains one integer  (), denoting the number appended in the -th task.

It is guaranteed that  are pairwise distinct.

The output contains  lines. Each line contains one integer, denoting the answer to the answer to the -th task.

9
11
4
5
14
1
9
19
8
10

0
0
0
0
2
3
3
6
7