[EC Final 2021] Future Coder

Luogu

IDLGP9880

Time1000ms

Memory1024MB

DifficultyP2

2021Special JudgeO2优化ICPCEC Final

Prof. Pang builds his famous coding team recently. To pursue a gold medal in ICPC, hundreds of pupils join his team. Unfortunately, one of Prof. Pang's students believes that for any integers $a$ and $b$, $a\times b\ge a+b$. To disprove this proposition, Prof. Pang writes $n$ numbers $a_1,a_2,\ldots, a_n$ on a paper and wants you to count how many pairs of numbers $(a_i, a_j)$ ($1\le i < j\le n$) satisfies $a_i\times a_j<a_i+a_j$. ## Input The first line contains a single integer $T$ ($1\le T\le 10^6$) denoting the number of test cases. For each test case, the first line contains a single integer $n$ ($1\le n\le 10^6$). The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9\le a_i\le 10^9$). It is guaranteed that the sum of $n$ over all test cases will not exceed $10^6$. ## Output For each test case, print one line containing the answer. [samples]

Samples

Input #1

2
8
3 -1 4 1 -5 9 2 -6
1
0

Output #1

19
0

API Response (JSON)

{
  "problem": {
    "name": "[EC Final 2021] Future Coder",
    "description": {
      "content": "Prof. Pang builds his famous coding team recently. To pursue a gold medal in ICPC, hundreds of pupils join his team. Unfortunately, one of Prof. Pang's students believes that for any integers $a$ and ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9880"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Prof. Pang builds his famous coding team recently. To pursue a gold medal in ICPC, hundreds of pupils join his team. Unfortunately, one of Prof. Pang's students believes that for any integers $a$ and ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments