#P18366. Puzzle IV

Puzzle IV

Puzzle IV

题目描述

给定一个长度为 nn 的整数序列 p1,p2,…,pnp_1,p_2,\ldots,p_n,初始时它是 1,2,…,n1,2,\ldots,n 的一个排列。你需要将它变成升序排列。

你可以将一个元素的当前值加到其相邻元素上,或者从其相邻元素中减去这个元素的当前值。具体地,可以执行以下操作:

  • a + b:令 pa←pa+pbp_a\leftarrow p_a+p_b。
  • a - b:令 pa←pa−pbp_a\leftarrow p_a-p_b。

每次操作都必须满足 ∣a−b∣=1|a-b|=1,下标从 1 开始。操作过程中,任意时刻所有元素的值都必须位于 [1,n][1,n] 中。

请输出不超过 2 500 0002\,500\,000 次操作,使最终序列为 1,2,…,n1,2,\ldots,n。不需要最小化操作次数;可以证明任意合法输入都有符合要求的方案。

输入格式

第一行一个整数 nn。

第二行 nn 个两两不同的整数 p1,p2,…,pnp_1,p_2,\ldots,p_n,表示初始排列。

输出格式

第一行输出一个整数 rr(0≤r≤2 500 0000\le r\le2\,500\,000),表示操作次数。

接下来 rr 行,每行按照 a + b 或 a - b 的格式描述一次操作,其含义如题目描述所示。每次操作必须满足 1≤a,b≤n1\le a,b\le n、∣a−b∣=1|a-b|=1,且操作后所有元素的值仍在 [1,n][1,n] 内。

执行全部操作后,必须满足 pi=ip_i=i。若存在多种合法方案,可以输出其中任意一种。

数据范围

  • 2≤n≤30 0002\le n\le30\,000。
  • 1≤pi≤n1\le p_i\le n,所有 pip_i 两两不同。
  • 每个输入文件只有一组数据。

样例输入 1

3
1 3 2

样例输出 1

3
2 - 3
3 + 2
2 + 1

样例解释

执行第一步后,序列变成 [1,1,2][1,1,2];执行第二步后变成 [1,1,3][1,1,3];执行第三步后变成 [1,2,3][1,2,3]。所有操作均满足相邻下标和值域要求。