Maximizing Resource Allocation Difference

In BlueQ Technology Company, two departments, \(A\) and \(B\), are competing for a newly developed AI chip research resource. In order to allocate the resource fairly over \(N\) days, the company devised a scheme as follows:

• Every morning, both department \(A\) and department \(B\) submit a demand level, which is an integer between \(1\) and \(N\) (inclusive). Each department must use every level exactly once during the \(N\) days.
• On day \(i\) (where \(1 \le i \le N\)), the department with the higher submitted level wins the day and receives \(i\) units of the resource. If both departments submit the same level, the resource for that day is wasted and neither department receives it.

Department \(A\) has an edge: they have a spy inside department \(B\) who reveals the submission order of their demand levels, given as a permutation \(P = (P_1, P_2, \dots, P_N)\), where \(P_i\) is the level submitted by \(B\) on day \(i\). With this information, department \(A\) can assign its own levels (a permutation of \(\{1,2,\dots,N\}\)) to maximize the difference between their total resource share and that of department \(B\).

Your task is to compute the maximum possible difference \(D\) defined as:

[ D = \text{(total resource units of department }A) - \text{(total resource units of department }B)]

when department \(A\) strategically assigns its demand levels knowing \(B\)'s order \(P\).

Note: On day \(i\):

• If \(A\)'s submitted level \(Q_i > P_i\), then department \(A\) wins and gains \(i\) units.
• If \(Q_i = P_i\), neither department gets resource.
• If \(Q_i < P_i\), then department \(B\) wins and gains \(i\) units (and department \(A\) effectively loses \(i\) units relative to \(B\)).

Determine the maximum difference \(D\) that department \(A\) can achieve.

inputFormat

The first line contains a positive integer \(N\) \((1 \le N)\) representing the number of days. The second line contains \(N\) distinct integers \(P_1, P_2, \dots, P_N\) (a permutation of \(\{1, 2, \dots, N\}\)) representing department \(B\)'s submission order.

outputFormat

Output a single integer, the maximum possible value of \(D\) (the difference between the total resources of department \(A\) and department \(B\)) that department \(A\) can achieve.

sample

2
2 1

1