1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
from sys import stdin, stdout

from dataclasses import dataclass

n = int(stdin.readline())
perm = [int(x) - 1 for x in stdin.readline().split()]

@dataclass
class Rect:
    x_min: int
    x_max: int
    y_min: int
    y_max: int

    @property
    def height(self):
        return self.y_max - self.y_min
    
    @property
    def width(self):
        return self.x_max - self.x_min
    
    def copy(self):
        return self.__class__(self.x_min, self.x_max, self.y_min, self.y_max)
    
    @classmethod
    def prefix_rect(cls, x_max, y_max):
        return cls(0, x_max, 0, y_max)
    
    @classmethod
    def suffix_rect(cls, x_min, y_min):
        return cls(x_min, n, y_min, n)
    

@dataclass
class ArraySummation:
    rect: Rect = Rect.prefix_rect(n, n)
    value: int = 0
    split_dir: bool = True
    split_val: int = n//2
    parts: tuple = ()

    def sum_rect(self, rect):
        if rect.width <= 0:
            return 0
        if rect.height <= 0:
            return 0
        return self.value + sum([child.sum_rect(splitted_rect)
                                 for child, splitted_rect in zip(self.parts, self.part_rect(rect))])
    
    def insert(self, x, y, val=1):
        if (self.rect.width == 1) & (self.rect.height == 1):
            self.value = val
            return
        if len(self.parts) == 0:
            self.create_parts()
        insert_child = self.part_by_point(x, y)
        self.parts[insert_child].insert(x, y, val)
    
    def part_rect(self, rect):
        if len(self.parts) == 0:
            return []
        return self.__generate_split(rect)
        
    def __generate_split(self, rect):
        if self.split_dir:
            left_r = rect.copy()
            right_r = rect.copy()
            left_r.x_max = min(rect.x_max, self.split_val)
            right_r.x_min = max(rect.x_min, self.split_val)
            return [
                left_r, right_r
            ]
        else:
            upper_r = rect.copy()
            lower_r = rect.copy()
            upper_r.y_min = max(rect.y_min, self.split_val)
            lower_r.y_max = min(rect.y_max, self.split_val)
            return [
                upper_r, lower_r
            ]
    
    def part_by_point(self, x, y):
        if self.split_dir:
            if x < self.split_val:
                return 0
            else:
                return 1
        else:
            if y >= self.split_val:
                return 0
            else:
                return 1

    def create_parts(self):
        self.split_dir = (self.rect.width >= self.rect.height)
        if self.split_dir:
            self.split_val = self.rect.x_min + self.rect.width // 2
        else:
            self.split_val = self.rect.y_min + self.rect.height // 2
        self.parts = tuple([self.__class__(rect=rect) for rect in self.__generate_split(self.rect)])

array_sum = ArraySummation()

for k, v in enumerate(perm):
    array_sum.insert(k, v)

def count_lines(rect):
    return array_sum.sum_rect(rect)

res = [0] * n
cache = {}

min_perm = [] # min of suffix
max_perm = [] # max of prefix
min_perm_rev = [] # min of suffix
max_perm_rev = [] # max of prefix

x = -1
for i in range(n):
    x = max(x, perm[i])
    max_perm.append(x)
x = n
for i in range(n-1, -1, -1):
    x = min(x, perm[i])
    min_perm.append(x)
min_perm = list(reversed(min_perm))
x = -1
for k in sorted(range(n), key=lambda x: perm[x]):
    x = max(x, k)
    max_perm_rev.append(x)
x = n
for k in sorted(range(n), key=lambda x: perm[x], reverse=True):
    x = min(x, k)
    min_perm_rev.append(x)
min_perm_rev = list(reversed(min_perm_rev))

for i in range(n):
    results_to_cache = []
    steps = step_lines = seen = 1
    min_line = max_line = i
    min_target = max_target = perm[i]
    search = True
    while(search):
        if (min_line, max_line, min_target, max_target) in cache:
            cached_steps, cached_value, cached_seen = cache[(min_line, max_line, min_target, max_target)]
            res[i] += cached_value + (cached_seen - seen) * (steps - cached_steps)
            seen = cached_seen
            search = False
            continue
        else:
            results_to_cache.append(((min_line, max_line, min_target, max_target), steps, res[i]))
        not_crossing = (count_lines(Rect.prefix_rect(min_line, min_target))
            + count_lines(Rect.suffix_rect(max_line+1, max_target+1)))
        step_lines = n - not_crossing - seen
        if step_lines == 0:
            search = False
            continue
        res[i] += steps * step_lines
        min_line, max_line, min_target, max_target = (
            min_perm_rev[min_target], max_perm_rev[max_target], min_perm[min_line], max_perm[max_line])
        steps += 1
        seen += step_lines
        if seen == n:
            search=False

    if len(cache)>10**9:
        cache = {}
    for key, steps, partial_value in results_to_cache:
        cache[key] = (steps, res[i] - partial_value, seen)

stdout.write(" ".join([str(x) for x in res]) + "\n")