시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 692 185 76 27.941%

문제

자연수 \(n\)개로 이루어진 배열 \(a_1,a_2,a_3,\dots ,a_n\)이 있다.

\(l\)부터 \(r\)까지 부분 배열은 \(a_l,a_{l+1},\dots , a_r\) 이다.

\(K_s\)는 부분 배열 안에 있는 자연수 \(s\)의 개수이다.

부분 배열의 힘이란 모든 자연수 \(s\)에 대해서, \(K_s \cdot K_s \cdot s\)를 합한 값이다.

배열과 부분 배열의 범위가 주어졌을 때, 각 부분 배열의 힘을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 \(n\)과 부분 배열의 개수 \(t\)가 주어진다. (1 ≤ \(n\), \(t\) ≤ 105) 둘째 줄에는 \(n\)개의 자연수 \(a_i\) (1 ≤ \(a_i\) ≤ 106) 가 주어진다.

다음 \(t\)개 줄에는 부분 배열의 범위 \(l_i\)와 \(r_i\)가 주어진다. (1 ≤ \(l_i\) ≤ \(r_i\) ≤ \(n\))

출력

입력으로 주어지는 각 부분 배열의 힘을 출력한다.

예제 입력 1

8 3
4 3 1 1 1 3 1 2
2 7
1 6
3 8

예제 출력 1

28
25
21
W3sicHJvYmxlbV9pZCI6Ijg0NjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMzBcdWM1ZjRcdWM3NTggXHVkNzk4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3OTBcdWM1ZjBcdWMyMTggXFwoblxcKVx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYzMwXHVjNWY0IFxcKGFfMSxhXzIsYV8zLFxcZG90cyAsYV9uXFwpXHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XFwobFxcKVx1YmQ4MFx1ZDEzMCBcXChyXFwpXHVhZTRjXHVjOWMwIFx1YmQ4MFx1YmQ4NCBcdWJjMzBcdWM1ZjRcdWM3NDAgXFwoYV9sLGFfe2wrMX0sXFxkb3RzICwgYV9yXFwpIFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XFwoS19zXFwpXHViMjk0IFx1YmQ4MFx1YmQ4NCBcdWJjMzBcdWM1ZjQgXHVjNTQ4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM3OTBcdWM1ZjBcdWMyMTggXFwoc1xcKVx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmQ4MFx1YmQ4NCBcdWJjMzBcdWM1ZjRcdWM3NTggXHVkNzk4XHVjNzc0XHViNzgwIFx1YmFhOFx1YjRlMCBcdWM3OTBcdWM1ZjBcdWMyMTggXFwoc1xcKVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFxcKEtfcyBcXGNkb3QgS19zIFxcY2RvdCBzXFwpXHViOTdjIFx1ZDU2OVx1ZDU1YyBcdWFjMTJcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMzMFx1YzVmNFx1YWNmYyBcdWJkODBcdWJkODQgXHViYzMwXHVjNWY0XHVjNzU4IFx1YmM5NFx1YzcwNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjMDEgXHViZDgwXHViZDg0IFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWQ3OThcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWQwNmNcdWFlMzAgXFwoblxcKVx1YWNmYyBcdWJkODBcdWJkODQgXHViYzMwXHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOCBcXCh0XFwpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBcXChuXFwpLCBcXCh0XFwpICZsZTsgMTA8c3VwPjU8XC9zdXA+KSBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFxcKG5cXClcdWFjMWNcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4IFxcKGFfaVxcKSAoMSAmbGU7IFxcKGFfaVxcKSAmbGU7IDEwPHN1cD42PFwvc3VwPikgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFxcKHRcXClcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmQ4MFx1YmQ4NCBcdWJjMzBcdWM1ZjRcdWM3NTggXHViYzk0XHVjNzA0IFxcKGxfaVxcKVx1YzY0MCBcXChyX2lcXClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFxcKGxfaVxcKSAmbGU7IFxcKHJfaVxcKSAmbGU7IFxcKG5cXCkpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWFjMDEgXHViZDgwXHViZDg0IFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWQ3OThcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijg0NjIiLCJwcm9ibGVtX2xhbmciOiIzIiwidGl0bGUiOiJQb3RcdTAxMTlcdTAxN2NuYSB0YWJsaWNhIiwiZGVzY3JpcHRpb24iOiI8cD5EYW5hIGplc3QgdGFibGljYSBcXChuXFwpIGxpY3piIG5hdHVyYWxueWNoIFxcKGFfMSxhXzIsYV8zLFxcZG90cyAsYV9uXFwpLiBSb3p3YVx1MDE3Y215IGZyYWdtZW50IHRlaiB0YWJsaWN5IG9kIFxcKGxcXCktdGVnbyBkbyBcXChyXFwpLXRlZ28gZWxlbWVudHU6IFxcKGFfbCxhX3tsKzF9LFxcZG90cyAsIGFfclxcKS4gT3puYWN6bXkgcHJ6ZXogXFwoS19zXFwpIGxpY3piXHUwMTE5IHd5c3RcdTAxMDVwaWVcdTAxNDQgbGljemJ5IFxcKHNcXCkgdyB0eW0gZnJhZ21lbmNpZS4gUG90XHUwMTE5Z1x1MDEwNSBmcmFnbWVudHUgdGFibGljeSBuYXp5d2FteSBzdW1cdTAxMTkgaWxvY3p5biZvYWN1dGU7dyBcXChLX3MgXFxjZG90IEtfcyBcXGNkb3Qgc1xcKSBwbyB3c3p5c3RraWNoIGxpY3piYWNoIG5hdHVyYWxueWNoIFxcKHNcXCkuIE9ibGljeiBwb3RcdTAxMTlnaSBwb2RhbnljaCBmcmFnbWVudCZvYWN1dGU7dy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5XIHBpZXJ3c3p5bSB3aWVyc3p1IHdlalx1MDE1YmNpYSB6bmFqZHVqXHUwMTA1IHNpXHUwMTE5IGR3aWUgbGljemJ5IGNhXHUwMTQya293aXRlIFxcKG5cXCkgaSBcXCh0XFwpICgxICZsZTsgXFwoblxcKSwgXFwodFxcKSAmbGU7IDEwPHN1cD41PFwvc3VwPikgb3puYWN6YWpcdTAxMDVjZSBkXHUwMTQydWdvXHUwMTViXHUwMTA3IHRhYmxpY3kgXFwoYVxcKSBvcmF6IGxpY3piXHUwMTE5IGZyYWdtZW50Jm9hY3V0ZTt3LCBkbGEga3Qmb2FjdXRlO3J5Y2ggbmFsZVx1MDE3Y3kgb2JsaWN6eVx1MDEwNyBwb3RcdTAxMTlnaS4gRHJ1Z2kgd2llcnN6IHphd2llcmEgXFwoblxcKSBsaWN6YiBuYXR1cmFsbnljaCBcXChhX2lcXCkgKDEgJmxlOyBcXChhX2lcXCkgJmxlOyAxMDxzdXA+NjxcL3N1cD4pLiBLYVx1MDE3Y2R5IHoga29sZWpueWNoIFxcKHRcXCkgd2llcnN6eSBvcGlzdWplIGplZG5lbiBmcmFnbWVudC4gT3BpcyBmcmFnbWVudHUgc2tcdTAxNDJhZGEgc2lcdTAxMTkgeiBkdyZvYWN1dGU7Y2ggbGljemIgY2FcdTAxNDJrb3dpdHljaCBcXChsX2lcXCksIFxcKHJfaVxcKSAoMSAmbGU7IFxcKGxfaVxcKSAmbGU7IFxcKHJfaVxcKSAmbGU7IFxcKG5cXCkpLCBrdCZvYWN1dGU7cmUgb3puYWN6YWpcdTAxMDUgaW5kZWtzIGplZ28gbGV3ZWdvIGkgcHJhd2VnbyBrcmFcdTAxNDRjYS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5OYSB3eWpcdTAxNWJjaXUgbmFsZVx1MDE3Y3kgd3lwaXNhXHUwMTA3IFxcKHRcXCkgd2llcnN6eSwgdyBcXChpXFwpLXR5bSBzcG9cdTAxNWJyJm9hY3V0ZTtkIG5pY2ggcG93aW5uYSB6bmFsZVx1MDE3YVx1MDEwNyBzaVx1MDExOSBqZWRuYSBsaWN6YmEgY2FcdTAxNDJrb3dpdGEgciZvYWN1dGU7d25hIHBvdFx1MDExOWR6aWUgXFwoaVxcKS10ZWdvIHogcG9kYW55Y2ggZnJhZ21lbnQmb2FjdXRlO3cuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDNmNFx1Yjc4MFx1YjRkY1x1YzViNCJ9XQ==

출처

Camp > POI Training Camp > ONTAK 2011 62번