F. Souvenirs

Codeforces

IDCF765F

Time3000ms

Memory512MB

Difficulty—

data structures

English · Original

Chinese · Translation

Formal · Original

Artsem is on vacation and wants to buy souvenirs for his two teammates. There are _n_ souvenir shops along the street. In _i_\-th shop Artsem can buy one souvenir for _a__i_ dollars, and he cannot buy more than one souvenir in one shop. He doesn't want to introduce envy in his team, so he wants to buy two souvenirs with least possible difference in price. Artsem has visited the shopping street _m_ times. For some strange reason on the _i_\-th day only shops with numbers from _l__i_ to _r__i_ were operating (weird? yes it is, but have you ever tried to come up with a reasonable legend for a range query problem?). For each visit, Artsem wants to know the minimum possible difference in prices of two different souvenirs he can buy in the opened shops. In other words, for each Artsem's visit you should find the minimum possible value of |_a__s_ - _a__t_| where _l__i_ ≤ _s_, _t_ ≤ _r__i_, _s_ ≠ _t_. ## Input The first line contains an integer _n_ (2 ≤ _n_ ≤ 105). The second line contains _n_ space-separated integers _a_1, ..., _a__n_ (0 ≤ _a__i_ ≤ 109). The third line contains the number of queries _m_ (1 ≤ _m_ ≤ 3·105). Next _m_ lines describe the queries. _i_\-th of these lines contains two space-separated integers _l__i_ and _r__i_ denoting the range of shops working on _i_\-th day (1 ≤ _l__i_ < _r__i_ ≤ _n_). ## Output Print the answer to each query in a separate line. [samples]

Artsem 正在度假，想为他的两名队友购买纪念品。街道上有 #cf_span[n] 家纪念品商店。在第 #cf_span[i] 家商店，Artsem 可以购买一件价格为 #cf_span[ai] 美元的纪念品，且每家商店最多只能购买一件。他不希望在团队中引起嫉妒，因此希望购买两件价格差最小的纪念品。 Artsem 已经访问了这条购物街 #cf_span[m] 次。奇怪的是，在第 #cf_span[i] 天，只有编号从 #cf_span[li] 到 #cf_span[ri] 的商店营业（奇怪？是的，但你有没有试过为一个区间查询问题编一个合理的背景故事？）。对于每次访问，Artsem 想知道在营业的商店中，他能购买的两件不同纪念品的最小价格差。换句话说，对于每次 Artsem 的访问，你需要找出满足 #cf_span[li ≤ s, t ≤ ri] 且 #cf_span[s ≠ t] 的最小可能值 #cf_span[|as - at|]。第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 105])。第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[a1], ..., #cf_span[an] (#cf_span[0 ≤ ai ≤ 109])。第三行包含查询次数 #cf_span[m] (#cf_span[1 ≤ m ≤ 3·105])。接下来的 #cf_span[m] 行描述查询。第 #cf_span[i] 行包含两个空格分隔的整数 #cf_span[li] 和 #cf_span[ri]，表示第 #cf_span[i] 天营业的商店范围 (#cf_span[1 ≤ li < ri ≤ n])。请在每行输出每个查询的答案。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 105])。第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[a1], ..., #cf_span[an] (#cf_span[0 ≤ ai ≤ 109])。第三行包含查询次数 #cf_span[m] (#cf_span[1 ≤ m ≤ 3·105])。接下来的 #cf_span[m] 行描述查询。第 #cf_span[i] 行包含两个空格分隔的整数 #cf_span[li] 和 #cf_span[ri]，表示第 #cf_span[i] 天营业的商店范围 (#cf_span[1 ≤ li < ri ≤ n])。 ## Output 请在每行输出每个查询的答案。 [samples]

Let $ a = [a_1, a_2, \dots, a_n] $ be an array of $ n $ integers, where $ a_i $ denotes the price of the souvenir at shop $ i $. Given $ m $ queries, each query is a range $ [l_i, r_i] $ with $ 1 \leq l_i < r_i \leq n $. For each query $ i $, define: $$ \text{answer}_i = \min_{\substack{l_i \leq s, t \leq r_i \\ s \neq t}} |a_s - a_t| $$ That is, compute the minimum absolute difference between any two distinct elements in the subarray $ a[l_i:r_i] $ (inclusive).

Samples

Input #1

8
3 1 4 1 5 9 2 6
4
1 8
1 3
4 8
5 7

Output #1

API Response (JSON)

{
  "problem": {
    "name": "F. Souvenirs",
    "description": {
      "content": "Artsem is on vacation and wants to buy souvenirs for his two teammates. There are _n_ souvenir shops along the street. In _i_\\-th shop Artsem can buy one souvenir for _a__i_ dollars, and he cannot buy",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF765F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Artsem is on vacation and wants to buy souvenirs for his two teammates. There are _n_ souvenir shops along the street. In _i_\\-th shop Artsem can buy one souvenir for _a__i_ dollars, and he cannot buy...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Artsem 正在度假，想为他的两名队友购买纪念品。街道上有 #cf_span[n] 家纪念品商店。在第 #cf_span[i] 家商店，Artsem 可以购买一件价格为 #cf_span[ai] 美元的纪念品，且每家商店最多只能购买一件。他不希望在团队中引起嫉妒，因此希望购买两件价格差最小的纪念品。\n\nArtsem 已经访问了这条购物街 #cf_span[m] 次。奇怪的是，在第 #cf_spa...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ a = [a_1, a_2, \\dots, a_n] $ be an array of $ n $ integers, where $ a_i $ denotes the price of the souvenir at shop $ i $.\n\nGiven $ m $ queries, each query is a range $ [l_i, r_i] $ with $ 1 \\le...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments