{"problem":{"name":"Sleep Log","description":{"content":"Takahashi keeps a sleep log. The log is represented as an odd-length sequence $A=(A _ 1(=0), A _ 2,\\ldots,A _ N)$, where odd-numbered elements represent times he got up, and even-numbered elements rep","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc305_d"},"statements":[{"statement_type":"Markdown","content":"Takahashi keeps a sleep log. The log is represented as an odd-length sequence $A=(A _ 1(=0), A _ 2,\\ldots,A _ N)$, where odd-numbered elements represent times he got up, and even-numbered elements represent times he went to bed. More formally, he had the following sleep sessions after starting the sleep log.\n\n*   For every integer $i$ such that $1\\leq i\\leq\\dfrac{N-1}2$, he fell asleep exactly $A _ {2i}$ minutes after starting the sleep log and woke up exactly $A _ {2i+1}$ minutes after starting the sleep log.\n*   He did not fall asleep or wake up at any other time.\n\nAnswer the following $Q$ questions. For the $i$\\-th question, you are given a pair of integers $(l _ i,r _ i)$ such that $0\\leq l _ i\\leq r _ i\\leq A _ N$.\n\n*   What is the total number of minutes for which Takahashi was asleep during the $r _ i-l _ i$ minutes from exactly $l _ i$ minutes to $r _ i$ minutes after starting the sleep log?\n\n## Constraints\n\n*   $3\\leq N\\lt2\\times10^5$\n*   $N$ is odd.\n*   $0=A _ 1\\lt A _ 2\\lt\\cdots\\lt A _ N\\leq10^9$\n*   $1\\leq Q\\leq2\\times10^5$\n*   $0\\leq l _ i\\leq r _ i\\leq A _ N\\ (1\\leq i\\leq Q)$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A _ 1$ $A _ 2$ $\\ldots$ $A _ N$\n$Q$\n$l _ 1$ $r _ 1$\n$l _ 2$ $r _ 2$\n$\\vdots$\n$l _ Q$ $r _ Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc305_d","tags":[],"sample_group":[["7\n0 240 720 1320 1440 1800 2160\n3\n480 1920\n720 1200\n0 2160","480\n0\n960\n\nTakahashi slept as shown in the following figure.\n![image](https://img.atcoder.jp/abc305/fe8152a63de7fea649d1d02197649a6a.png)\nThe answers to each question are as follows.\n\n*   Between $480$ minutes and $1920$ minutes after starting the sleep log, Takahashi slept from $480$ minutes to $720$ minutes, from $1320$ minutes to $1440$ minutes, and from $1800$ minutes to $1920$ minutes in $3$ sleep sessions. The total sleep time is $240+120+120=480$ minutes.\n*   Between $720$ minutes and $1200$ minutes after starting the sleep log, Takahashi did not sleep. The total sleep time is $0$ minutes.\n*   Between $0$ minutes and $2160$ minutes after starting the sleep log, Takahashi slept from $240$ minutes to $720$ minutes, from $1320$ minutes to $1440$ minutes, and from $1800$ minutes to $2160$ minutes in $3$ sleep sessions. The total sleep time is $480+120+360=960$ minutes.\n\nTherefore, the three lines of the output should contain $480$, $0$, and $960$."],["21\n0 20 62 192 284 310 323 324 352 374 409 452 486 512 523 594 677 814 838 946 1000\n10\n77 721\n255 541\n478 970\n369 466\n343 541\n42 165\n16 618\n222 592\n730 983\n338 747","296\n150\n150\n49\n89\n20\n279\n183\n61\n177"]],"created_at":"2026-03-03 11:01:13"}}