Robot Marathon: Best and Worst Rankings

There are \(N\) robot competitors in a marathon, numbered \(1, 2, \ldots, N\). The race track has \(N\) lanes numbered \(1, 2, \ldots, N\), and each competitor \(i\) occupies lane \(i\). Every lane has the same length. It is known that competitor \(i\) needs \(a_i\) seconds to finish the race once he starts running.

At the starting line of each lane there is a starting horn. However, not all horns are activated – some have been turned off by the referee as a prank.

At the given moment, all activated horns fire simultaneously and send the starting signal. The signal then propagates sideways along the lanes at a speed of \(1\) lane per second. In other words, if only lane \(i\)'s horn fires then competitor \(i\) starts immediately at time \(0\), competitor \(i-1\) and \(i+1\) will start at time \(1\), competitors \(i-2\) and \(i+2\) will start at time \(2\), and so on.

If in a specific scenario the horn of lane \(j\) is activated then competitor \(j\) starts instantly; if not, the competitor starts when the signal reaches his lane from the nearest lane with an activated horn. Formally, if the set of lanes with an activated horn is \(S\) (with \(S\) a nonempty subset of \(\{1,2,\ldots,N\}\)), then competitor \(i\) starts at time \(x_i = \min_{j\in S} |i-j|\) and finishes at time \(f_i = a_i + x_i\>.

The ranking is determined by the finishing times: the smaller \(f_i\) is, the higher the rank; if several competitors have the same finishing time, they share the same rank which is \(1+\) (number of competitors with strictly smaller finishing time).

Since the activation pattern \(S\) can be chosen arbitrarily (subject only to \(S\ne\emptyset\)), each competitor can potentially achieve different rankings. In particular, a competitor's best ranking is determined by choosing an activation pattern that minimizes his finishing time relative to the others, and the worst ranking is determined by a pattern that maximizes his finishing time relative to the others.

Show that:

• For the best scenario for competitor \(i\), choose \(S = \{i\}\). Then \(x_i=0\) so \(f_i = a_i\) and for any other competitor \(j\), \(f_j = a_j + |j-i|\).
• For the worst scenario, exclude competitor \(i\} from \(S\) and choose an activation lane \(k\) (with \(k\ne i\)) that maximizes the number of competitors finishing before \(i\). When \(S = \{k\}\), for competitor \(i\) we have \(f_i = a_i + |i-k|\) and for any competitor \(j\), \(f_j = a_j + |j-k|\).

Your task is to compute, for each competitor \(i\), the best ranking and the worst ranking he can achieve by an appropriate choice of \(S\). More precisely, for each \(i\) (\(1 \le i \le N\)):

• Best rank: \(1 + \#\{ j : a_j + |j-i| < a_i \}\).
• Worst rank: \(1 + \max_{k\in\{1,\ldots,N\},\; k\ne i} \#\{ j : a_j + |j-k| < a_i + |i-k| \}\).

Input: The first line contains an integer \(N\) (the number of competitors). The second line contains \(N\) space‐separated integers \(a_1, a_2, \ldots, a_N\), where \(a_i\) is the number of seconds competitor \(i\) needs to complete his lane once he starts running.

Output: Print \(N\) lines. The \(i\)-th line should contain two integers separated by a space: the best ranking and the worst ranking for competitor \(i\>.

Note: In case of a tie in finishing times, competitors share the rank which is \(1+\) (the number of competitors with strictly smaller finishing time).

inputFormat

The input consists of two lines. The first line contains a single integer \(N\) (\(1 \le N \le\) some limit). The second line contains \(N\) integers \(a_1, a_2, \ldots, a_N\) separated by spaces.

outputFormat

Output \(N\) lines. For each competitor \(i\) (from 1 to \(N\)), output two integers separated by a space: the best rank and the worst rank that competitor \(i\) can achieve.

sample

1
5

1 1

</p>