← 返回题目列表

AtCoder · agc007_b

B. 构造序列

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给你一个排列 p 的集合 {1, 2, ..., N}。请构造两个正整数序列 a_1, a_2, ..., a_N 和 b_1, b_2, ..., b_N 满足以下条件:

  • 1 \leq a_i, b_i \leq 10^9 对于所有人 i
  • a_1 < a_2 < ... < a_N
  • b_1 > b_2 > ... > b_N
  • a_{p_1}+b_{p_1} < a_{p_2}+b_{p_2} < ... < a_{p_N}+b_{p_N}

约束

  • 2 \leq N \leq 20,000
  • p 是集合 { 的排列1, 2, ..., N}

输入

输入由标准输入按以下格式给出:

N
p_1 p_2 ... p_N 

输出

输出由两行组成。第一行包含 a_1, a_2, ..., a_N 用空格分隔。第二行包含 b_1, b_2, ..., b_N 用空格分隔。

可以证明,对于任何满足约束的输入,总是存在一个解。


示例输入 1

2
1 2

示例输出 1

1 4
5 4

a_1 + b_1 = 6 和 a_2 + b_2 = 8。所以这个输出满足所有条件。


示例输入 2

3
3 2 1

示例输出 2

1 2 3
5 3 1

示例输入 3

3
2 3 1

示例输出 3

5 10 100
100 10 1