33OJ
登录 注册

#P3962. [TJOI2013] 数字根

[TJOI2013] 数字根

题目描述

一个数字的数字根定义为:这个数字每一位的数字加起来求和,反复这个过程直到和小于 1010。例如,6435764357 的数字根为 77,因为 6+4+3+5+7=256+4+3+5+7=25,2+5=72+5=7 个区间的数字根定义为这个区间所有数字和的数字根。

给定一个序列 A1,A2,A3,⋯ ,AnA_1,A_2,A_3,\cdots,A_n,你需要回答一些询问。每一个询问给定个区间 [L,R][L,R],求出这个区间所有连续子区间里最大的前 55 个不同的数字根,不够 55 个的用 −1-1 补全。

输入格式

第一行一个整数 NN,表示序列的长度。

第二行是 NN 个整数 Ai(0≤Ai<109)A_i(0 \le A_i < 10^9)。第三行是一个整数 QQ 表示询问次数。接下来 QQ 行,每一行两个正整数 l,rl,r,表示询问区间。(1≤l≤r≤N)(1 \le l \le r \le N)

输出格式

QQ 行,表示每一个查询区间所有连续子区间里最大的前 55 个不同的数字根,按降序输出,输出用空格隔开。

5
101 240 331 4 52
3
1 3
4 5
1 5
8 7 6 4 2
7 4 2 -1 -1
9 8 7 6 4

提示

样例解释

第一个查询区间 [1,3][1,3],它的连续子区间有 [1,1],[2,2],[3,3],[1,2],[2,3],[1,3][1,1],[2,2],[3,3],[1,2],[2,3],[1,3]。可对应的数字根分别为 2,6,7,8,4,62,6,7,8,4,6。所以最大的 55 个是 8,7,6,4,28,7,6,4,2。

数据范围

30%30\% 的数据,N≤1000N \le 1000;Q≤1000Q \le 1000。

100%100\% 的数据,N≤100000N \le 100000;Q≤100000Q \le 100000。